Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
TOPSORTL - Porządek leksykograficzny w grafie |
Mateusz chce zwiedzić miasta numerowane liczbami 0, 1, ..., n-1. Ma jednak narzucone przez kogoś tam relacje pomiędzy miastami. Relacja ta nazywa się relacją poprzedzania. Na przykład chcąc zwiedzić 5 miast : 0,1,2,3,4 mając narzucone relacje 1 przed 3 0 przed 4 2 przed 3 Mateusz może odwiedzić wszystkie miasta w kolejności np. 2 1 0 3 4 Twoim zadaniem jest dla danych relacji poprzedzania, znaleźć kolejność miast, które może odwiedzić Mateusz. W sytuacji, gdy nie możliwe jest odwiedzenie wszystkich miast wypisz -1. W sytuacji, gdy możliwych jest wiele odpowiedzi, wypisz najmniejszą leksykograficznie.
Input
W pierwszym wierszu dane są dwie liczby n i m. 1 <= n <= 10^6, 0 <= m <= 10^6. W kolejnych m-wierszach znajdują się pary liczb a b (oddzielone spacją) oznaczające, że miasto a należy odwiedzić przed miastem b. ( 0<= a, b < n ).
Output
Wypisz -1 jeśli niemożliwe jest zwiedzenie wszystkich miast zgodnie z opisem powyżej. Wypisz wszystkie miasta w jednym wierszu oddzielając ich numery pojedynczym odstępem w kolejności jakiej powinien zwiedzać je Mateusz. W sytuacji, gdy możliwych jest wiele odpowiedzi, wypisz najmniejszą leksykograficznie
Przykład 1
Wejście: 13 12 1 2 2 3 2 4 4 0 2 5 5 6 6 7 7 8 8 9 8 10 7 11 11 12 Przykładowe wyjście: 1 2 3 4 0 5 6 7 8 9 10 11 12
Przykład 2
Wejście: 3 3 0 1 1 2 2 1 Wyjście: -1
Dodane przez: | Rafal Nowak |
Data dodania: | 2007-03-21 |
Limit czasu wykonania programu: | 1s-1.187s |
Limit długości kodu źródłowego | 5000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ADA95 ASM32 BASH BF CSHARP C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN GOSU HASK ICON ICK JAVA JS-RHINO LUA NEM NICE OCAML PAS-GPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST WHITESPACE |
Pochodzenie: | Własne |