The sequence $a_1, a_2, ..., a_n$ is called a permutation, if it contains every integer from $1$ to $n$. The permutation of vertices $a_1, a_2, ..., 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_1, a_2, ..., a_n$ is lexicographically smaller than the permutation $b_1, b_2, ..., b_n$, if there exists $m$ such that $a_i = b_i$ for every $1 \le 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. \InputFile The first line contains three integers $n, m$ and $k\:(1 \le n \le 10^5, 0 \le m, k \le 10^5)$ --- 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_i$, describing directed edge from $u_i$ to $v_i\:(1 \le u_i, v_i \le n)$. The graph has no cycles. \OutputFile 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 \le x \le 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. \includegraphics{https://static.eolymp.com/content/un/un5hgs7mbh5u3b20f8t48kb1nk.gif}