TopCoder

Cheng0928
退休 ~

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

75.0% (3/4)

Tags

Description

uu 最近發現,好像有越來越多情侶產生了,這意味著,還有許多奇奇怪怪的關係線可能還沒被發現。
起初,uu 想知道,總共會有多少人可以變成情侶。
於是,uu 開始調查身邊的人$\dots$

uu 總共有 $n$ 位好友,依序編號 $1$ 到 $n$。
並且總共有 $m$ 條關係,第 $i$ 對關係表示 $a_i$ 喜歡 $b_i$,
當兩個人互相喜歡, uu 就當作他們是情侶。

uu 將關係整理好後,想請你幫他看看,總共有多少對情侶。
假設有 $k$ 對情侶,八卦的初八想知道這 $k$ 對分別有誰。


對於所有測試資料:
$1 \le n \le 10$$5$
$1 \le m \le n$
$1 \le a_i , \ b_i \le n$

保證 $a_i$ 不重複且 $a_i \ne b_i$

Input Format

輸入共 $1 + m$ 行,
第一行有兩個整數,依序為 $n ,\ m$,
接下來有 $m$ 行,
第 $i+1$ 行有兩個數字 $a_i ,\ b_i$。

Output Format

輸出共 $1+k$ 行,
第一行僅一個數字 $k$,表示有多少對情侶。
接下來共 $k$ 行,
第 $i+1$ 行有兩個整數 $u_i ,\ v_i$,表示第 $i$ 對情侶的號碼,
其中必須保證 $u_i \lt v_i$ 且當 $1 \le i \le n-1$ 時需要滿足 $u_i \lt u_{i+1}$。

Sample Input 1

4 3
1 2
2 3
3 4

Sample Output 1

0

Sample Input 2

3 3
1 2
2 1
3 1

Sample Output 2

1
1 2

Hints

20 <-> 34

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~4 題目範圍限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1 2
1 1000 65536 65536 1 2
2 1000 65536 65536 2
3 1000 65536 65536 2
4 1000 65536 65536 2