~/algor $ cat masalalar/topologik-saralash
Graf-04
Topologik saralash
Muallif:
Iqbolshoh Ilhomjonov
O'rtacha
1000 ms
128 MB
59%
$n$ ta cho'qqi va $m$ ta yo'naltirilgan qirradan iborat graf berilgan. Cho'qqilar $1$ dan $n$ gacha raqamlangan. Hamma cho'qqilarni shunday tartibda yozing (topologik tartib): har bir $u \to v$ qirra uchun $u$ cho'qqi $v$ dan oldin keladi. Bir nechta to'g'ri tartib bo'lsa, leksikografik eng kichigini chiqaring. Grafda tsikl bo'lsa, $-1$ chiqaring.
Kiruvchi ma'lumotlar
Birinchi qatorda ikkita butun son: $n$ va $m$. Keyingi $m$ ta qatorning har birida ikkita natural son: $u$ va $v$ — $u \to v$ qirra.
Chiquvchi ma'lumotlar
Bitta qatorda bo'sh joy bilan ajratilgan $n$ ta butun son — topologik tartib, yoki tsikl bo'lsa $-1$.
Izoh
$1 \le n \le 10^{5}$
$0 \le m \le 2 * 10^{5}$
$1 \le u, v \le n$
Misollar
Kirish #1
4 3 1 2 2 4 3 4
Chiqish #1
1 2 3 4
Kirish #2
3 3 1 2 2 3 3 1
Chiqish #2
-1