Граф#7618

Граф

1 секунда

128 мегабайтів

Складна

Послідовність $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n називається перестановкою, якщо вона містить кожне ціле число від $1$ до $n$ рівно один раз.

Перестановка вершин $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n називається топологічним сортуванням орієнтованого графа, якщо для кожного орієнтованого ребра з $u$ до $v$ вершина $u$ розташована в цій перестановці раніше за вершину $v$ .

Перестановка $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n лексикографічно менша за перестановку $b_{1}, b_{2}, \dots, b_{n}$ b_1, b_2, \ldots, b_n, якщо існує такий індекс $m$ , що $a_{i} = b_{i}$ a_i = b_i для всіх $1 \leq i < m$ 1 \le i < m та $a_{m} < b_{m}$ a_m < b_m.

Задано орієнтований ациклічний граф. Додайте до нього не більше $k$ орієнтованих ребер так, щоб отриманий граф залишився ациклічним, а його лексикографічно найменше топологічне сортування було якомога більшим.

Вхідні дані

Перший рядок містить три цілих числа $n$ , $m$ та $k (1 \leq n \leq 1 0^{5}, 0 \leq m, k \leq 1 0^{5})$ k~(1 \le n \le 10^5, 0 \le m, k \le 10^5) — кількість вершин та орієнтованих ребер у вихідному графі, а також максимальну кількість орієнтованих ребер, яку дозволено додати.

Кожен з наступних $m$ рядків містить два цілих числа $u_{i}$ u_i та $v_{i} (1 \leq u_{i}, v_{i} \leq n)$ v_i~(1 \le u_i, v_i \le n), що описують орієнтоване ребро з $u_{i}$ u_i до $v_{i}$ v_i.

Гарантується, що граф не містить циклів.

Вихідні дані

У першому рядку виведіть $n$ цілих чисел — лексикографічно найменше топологічне сортування зміненого графа. У другому рядку виведіть одне ціле число $x$ $(0 \leq x \leq k)$ (0 \le x \le k) — кількість доданих орієнтованих ребер. У кожному з наступних $x$ рядків виведіть опис одного доданого ребра у тому самому форматі, що й у вхідних даних.

Приклади

Приклад 1

Приклад 2