408354: GYM103104 E Revue

Revues are enchanting stage performances with songs and dances. The path to Topstar will unfold for the stage girl who presents Revue's most brilliant show.

A total of $$$n\;(1\leq n\leq10^6)$$$ stage girls from Seisho Music Academy, with student numbers $$$1$$$ through $$$n$$$, participated in the Talking Giraffe's auditions. Each stage girl has a radiance value $$$r_i\;(i=1,\ldots,n)$$$. They all have their own unique charm, so the radiance value is pairwise distinct. The auditions are made up of a number of Revue plays, and in each Revue, the winning girl gets more shine. But radiance doesn't come out of nowhere, it doesn't go out of nowhere, it just passes from one stage girl to another. In a Revue, if stage girl $$$x$$$ beats $$$y$$$, this is the change in their radiance: $$$$$$ \begin{cases} r_x\leftarrow\max\{r_x,r_y\}\\ r_y\leftarrow\min\{r_x,r_y\} \end{cases} $$$$$$

Stage Girls' radiance is not easy to read, so you don't know the exact number of $$$r_i$$$. However, you get the script and know the next sequence of $$$m\;(0\leq m\leq10^6)$$$ Revues, with the winner $$$x_i$$$ and loser $$$y_i\;(i=1,\ldots,m)$$$. You can continue to arrange $$$w$$$ Revues in sequence at the end of the script, with the corresponding winners and losers. So there are total $$$m+w$$$ Revues in the auditions.

But the stage the Talking Giraffe wants to show is the stage of fate that no one can predict. Depending on the choice of play, the stages can be quite diverse. The stage girls at Seisho Music Academy will be absent from $$$k\;(0\leq k\leq10^6)$$$ shows, which means up to $$$k$$$ shows of the total $$$m+w$$$ shows in Revue will NOT take place, and you don't know which shows they are.

Karen Aijo, whose student number is 1, did not want to fight with the partners in this baffling selection and become a lonely Topstar, she just wants to let everyone stars shine. If she doesn't get the maximum radiance value after the auditions, she won't be able to stand on the Starlight stage with Hikari-chan. So, she wants to know, after all the Revues are over, will she be able to get the biggest radiance value of all the stage girls?

Please write a program, help BaKaren, cleverly add $$$w$$$ Revue at the end of the script and make add session $$$w$$$ as little as possible, with the every possible initial value of $$$r_i$$$ and Revue session that won't take place (at most $$$k$$$), to let Karen Aijo eventually will surely be able to get the biggest radiance value, so that the all stars shine.

The first line contains three integers $$$n\;(1\leq n\leq 10^6),\;m\;(0\leq m\leq 10^6),\;k\;(0\leq k\leq10^6)$$$, which meanings are described in the statement above.

The next $$$m$$$ lines contain two integers $$$x_i,\;y_i\;(1\leq x_i,y_i\leq n,\;x_i\neq y_i,\;i=1,\ldots,m)$$$ in each line, representing the winner and the loser in each Revue the Talking Giraffe arranged.

Output an integer $$$w\;(w\geq0)$$$ on the first line, representing the minimum number of session $$$w$$$ to be added at the end of the script.

If $$$w\leq1000$$$, then output $$$w$$$ lines, each line contains two integers $$$x,\;y\;(1\leq x,y\leq n,\;x\neq y)$$$, representing winners and losers of each Revue you arranged. You can output ANY possible solution.

5 4 0
2 3
4 5
4 1
1 3

2
4 2
1 4

5 4 1
2 3
4 5
4 1
1 3

5
1 2
4 5
1 4
2 4
1 2

For the first example case, the final sequence of Revues is [(2, 3), (4, 5), (4, 1), (1, 3), (4, 2), (1, 4)], and it's easy to verify that the maximum radiance will always be passed to person 1.

But if the Revue (1, 4) did not take place, the maximum radiance might remain at person 2 or person 4. That is the problem you face at the second example case.