問題文

$N$ 頂点 $0$ 辺のグラフがあります。このグラフにいくつかの有向辺を追加し、以下の条件が満たされるようにしたいです。

• 全ての整数 $i\ (1 \le i \le M)$ について、頂点 $U_i$ から頂点 $V_i$ への有向パスが存在する。

この条件が満たされるような有向辺の追加方法のうち、追加する辺数が最小であるようなものを一つ示してください。

入力

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

• 入力はすべて整数
• $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$
• $i \neq j$ であれば $(U_i,V_i) \neq (U_j,V_j)$

出力

$1$ 行目には追加する辺数 $K$ を、$i+1\ (1 \le i \le K)$ 行目には $i$ 番目の有向辺を頂点 $A_i$ から頂点 $B_i$ に張るとして $A_i$ と $B_i$ を空白区切りで出力し、最後に改行してください。

追加する辺数が最小であるような有向辺の追加方法が複数ある場合はどれを出力しても構いません。ただし $1 \le A_i,B_i \le N$ が満たされていなければいけません。

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

サンプル

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