Grafo#7618

Grafo

1 secondo

128 megabyte

Difficile

Последовательность $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$ ориентированных рёбер так, чтобы полученный граф остался ациклическим, а его лексикографически наименьшая топологическая сортировка была как можно больше.

Input

Первая строка содержит три целых числа $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.

Гарантируется, что граф не содержит циклов.

Output

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

Esempi

Esempio 1

Esempio 2