Graph#7618
The sequence a_1, a_2, \ldots, a_n is called a permutation if it contains every integer from to exactly once.
A permutation of vertices a_1, a_2, \ldots, a_n is a topological sort of a directed graph if, for every directed edge from to , vertex appears before vertex in this permutation.
A permutation a_1, a_2, \ldots, a_n is lexicographically smaller than a permutation b_1, b_2, \ldots, b_n if there exists an index such that a_i = b_i for all 1 \le i < m and a_m < b_m.
You are given a directed acyclic graph. Add at most directed edges to it so that the resulting graph remains acyclic and its lexicographically smallest topological sort is as large as possible.
The first line contains three integers , and k~(1 \le n \le 10^5, 0 \le m, k \le 10^5) — the number of vertices, the number of directed edges in the original graph, and the maximum number of directed edges you are allowed to add.
Each of the next lines contains two integers u_i and v_i~(1 \le u_i, v_i \le n), describing a directed edge from u_i to v_i.
It is guaranteed that the graph contains no cycles.
In the first line, print integers — the lexicographically smallest topological sort of the modified graph. In the second line, print a single integer (0 \le x \le k) — the number of added directed edges. Each of the next lines should describe one added edge in the same format as in the input.
Example 1
Example 2