Последовательность a1,a2,...,an называется перестановкой, если она содержит все целые числа от 1 до n.
Перестановка вершин a1,a2,...,an называется топологической сортировкой ориентированного графа, если для каждого ориентированного ребра из u в v вершина u идет раньше v в этой перестановке.
Перестановка a1,a2,...,an лексикографически меньше перестановки b1,b2,...,bn, если существует m такое что ai=bi для каждого 1≤i<m, и при этом am<bm.
В заданном ориентированном ациклическом графе добавить не более k ориентированных ребер так, чтобы полученный граф все так же не имел циклов, а его лексикографически наименьшая топологическая сортировка была бы максимально возможной.
Первая строка содержит три целых числа n,m и k(1≤n≤105,0≤m,k≤105) — количество вершин и ориентированных ребер в графе, а также число ориентированных ребер, которое разрешено добавить.
Каждая из следующих m строк содержит два целых числа ui,vi, задающих ориентированное ребро из ui в vi(1≤ui,vi≤n).
Граф не имеет циклов.
В первой строке вывести n чисел - лексикографически наименьшую топологическую сортировку модифицированного графа. Во второй строке вывести число x(0≤x≤k) — количество добавленных ориентированных ребер. Следующие x строк содержат добавленные ориентированные ребра в том же формате как и во входных данных.