an is called a permutation, if it contains every integer from 1 to n.
The permutation of vertices
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.
an is lexicographically smaller than the permutation
bn, if there exists m such that
bi for every 1 ≤ i < m and
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 (1 ≤ n ≤ 100 000, 0 ≤ m, k ≤ 100 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
vi, describing directed edge from
vi (1 ≤
vi ≤ n).
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 (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.
5 3 2 1 4 4 2 1 3
5 1 4 2 3 2 5 1 2 3
2 2 20 1 2 1 2
1 2 0