Topological sort


The sequence a1, a2, ..., an is called a permutation, if it contains every integer from 1 to n.

The permutation of vertices a1, a2, ..., an 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 a1, a2, ..., an is lexicographically smaller than the permutation b1, b2, ..., bn, if there exists m such that ai = bi for every 1i < m and am < bm.

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 contains three integers n, m and k (1n100 000, 0m, k100 000) - the number of vertices and directed edges in the original graph, and the number of directed edges, that you are allowed to add.

Each of the following m lines contains two integers ui, vi, describing directed edge from ui to vi (1ui, vin).

The graph has no cycles.


The first line should contain n integers - the lexicographically minimal topological sort of the modified graph. The second line should contain a single integer x (0xk) - 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.

Time limit 1 second
Memory limit 128 MiB
Input example #1
5 3 2
1 4
4 2
1 3
Output example #1
5 1 4 2 3
5 1
2 3
Input example #2
2 2 20
1 2
1 2
Output example #2
1 2
Source 2015 ACM NEERC, Northern Subregion, October 24, Problem G