Граф
Граф
Последовательность 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 строк содержат добавленные ориентированные ребра в том же формате как и во входных данных.
Пример
5 3 2 1 4 4 2 1 3
5 1 4 2 3 2 5 1 2 3
2 2 20 1 2 1 2
1 2 0