A factory has n assembly stations, numbered 1 to n, that must each be commissioned (brought online) exactly once. There are m precedence rules; rule u v means station u must be commissioned strictly before station v. Rules may repeat, and a rule may even name the same station twice (u v with u = v), which makes commissioning impossible.
If at least one valid commissioning order (a permutation of all n stations honoring every rule) exists, print the LEXICOGRAPHICALLY SMALLEST such order, as n space-separated station numbers. If no valid order exists, print -1 instead.
Input format
Line 1: two integers n and m — number of stations (1-indexed) and number of rules.
Next m lines: two integers u v — station u must be commissioned before station v.
Output format
Either n space-separated integers (the lexicographically smallest valid order), or the single value -1 if no valid order exists.
Constraints
- 1 ≤ n ≤ 8
- 0 ≤ m ≤ 20
- 1 ≤ u, v ≤ n