11472번 - Graph 스페셜 저지다국어

문제

The sequence a₁, a₂, . . . , a_n is called a permutation, if it contains every integer from 1 to n.

The permutation of vertices a₁, a₂, . . . , a_n is a topological sort of a directed graph, if for every directed edge from u to v, vertex u comes before v in this permutation.

The permutation a₁, a₂, . . . , a_n is lexicographically smaller than the permutation b₁, b₂, . . . , b_n, if there exists m such that a_i = b_i for every 1 ≤ i < m and a_m < b_m.

Given a directed acyclic graph, add at most k directed edges to it in such a way, that the resulting graph still has no cycles and the lexicographically minimal topological sort of the graph is maximum possible.

입력

The first line of the input file contains three integers n, m and k — the number of vertices and directed edges in the original graph, and the number of directed edges, that you are allowed to add (1 ≤ n ≤ 100 000; 0 ≤ m, k ≤ 100 000).

Each of the following m lines contains two integers u_i, v_i, describing directed edge from u_i to v_i (1 ≤ u_i, v_i ≤ n).

The graph has no cycles.

출력

The first line of the output file should contain n integers — the lexicographically minimal topological sort of the modified graph. The second line should contain a single integer x (0 ≤ x ≤ k) — the number of directed edges to add. The following x lines of the output should contain description of added directed edges in the same format as in the input file.

제한

힌트