Problem Statement

There is a graph with $N$ vertices and $0$ edges. You want to add some directed edges to this graph so that the following condition is satisfied.

• For every integer $i\ (1 \le i \le M)$, there exists a directed path from vertex $U_i$ to vertex $V_i$.

Among the ways of adding directed edges that satisfy this condition, show one that minimizes the number of added edges.

Input

$N$ $M$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_M$ $V_M$

• All inputs are integers.
• $2 \le N \le 2 \times 10^5$
• $1 \le M \le 2 \times 10^5$
• $1 \le U_i,V_i \le N$
• $U_i \neq V_i$
• If $i \neq j$, then $(U_i,V_i) \neq (U_j,V_j)$

Output

On line $1$, output the number of added edges $K$. On line $i+1\ (1 \le i \le K)$, output $A_i$ and $B_i$ separated by a space, where the $i$-th directed edge goes from vertex $A_i$ to vertex $B_i$. End the output with a newline.

If there are multiple ways of adding directed edges that minimize the number of added edges, you may output any of them. However, $1 \le A_i,B_i \le N$ must be satisfied.

$K$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_K$ $B_K$

Sample

3 2
1 2
1 3

2
1 2
1 3

8 10
4 5
3 4
6 8
5 7
2 4
1 6
3 6
1 8
2 8
1 2

7
3 1
1 6
6 2
2 8
8 4
4 5
5 7