Граф

Последовательность $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$ строк содержат добавленные ориентированные ребра в том же формате как и во входных данных.

Примеры