eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Граф

Граф

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

Пример

Входные данные #1
5 3 2
1 4
4 2
1 3
Выходные данные #1
5 1 4 2 3
2
5 1
2 3
Входные данные #2
2 2 20
1 2
1 2
Выходные данные #2
1 2
0
Источник 2015 ACM NEERC, Northern Subregion, October 24, Problem G