# Topological sort

# Graph

The sequence `a`

, _{1}`a`

, ..., _{2}`a`

is called a permutation, if it contains every integer from _{n}**1** to **n**.

The permutation of vertices `a`

, _{1}`a`

, ..., _{2}`a`

is a topological sort of a directed graph, if for every directed edge from _{n}**u** to **v**, vertex **u** comes before **v** in this permutation.

The permutation `a`

, _{1}`a`

, ..., _{2}`a`

is lexicographically smaller than the permutation _{n}`b`

, _{1}`b`

, ..., _{2}`b`

, if there exists _{n}**m** such that `a`

= _{i}`b`

for every _{i}**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.

#### Input

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 `u`

, _{i}`v`

, describing directed edge from _{i}`u`

to _{i}`v`

(_{i}**1** ≤ `u`

, _{i}`v`

≤ _{i}**n**).

The graph has no cycles.

#### Output

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