Граф

Послідовність $a_1,a_2,...,a_n$ називається перестановкою, якщо вона містить усі цілі числа від $1$ до $n$.

Перестановка вершин $a_1,a_2,...,a_n$ є топологічним сортуванням орієнтованого графа, якщо для кожного орієнтованого ребра з $u$ в $v$ вершина $u$ передує $v$ в цій перестановці.

Перестановка $a_1,a_2,...,a_n$ лексикографічно менша перестановки $b_1,b_2,...,b_n$, якщо існує таке $m$, що $a_i=b_i$ для всіх $1\le i<m$, і при цьому $a_m<b_m$.

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

Вхідні дані

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

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

Граф не має циклів.

Вихідні дані

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

Приклади