NTUCPC Speed Run! #1 比賽已結束，感謝大家的參與！題目連結
IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
255 . 殿壬的王國
TopCoder
Tags
Description
殿壬的王國是一個很殿的王國，他的王國有 $N$ 座城市和 $M$ 條路，城市編號為 $1, 2, \ldots, N$，每一條路都連接著兩座不同的城市而且都是雙向的，並且沒有兩座城市之間有兩條以上的道路，因為昨天殿壬很殿，所以他的王國從任何一座城市出發都可以到其他所有城市。然而今天因為殿壬很殿，他想要把每一條路都改成單向的，但是這樣可能會讓某一座城市沒辦法到達另外一座城市，所以他想要再蓋幾條單向道路讓從任何一座城市出發都可以到達其他所有城市。請問殿壬至少還需要蓋幾條道路呢？請幫幫他。
Input Format
輸入第一行有兩個正整數 $N, M$，代表殿壬的王國有 $N$ 座城市和 $M$ 條雙向道路。
接下來 $M$ 行的第 $i$ 行有兩個正整數 $x_i, y_i$，代表這座城市的第 $i$ 條道路連接著第 $x_i$ 座城市以及第 $y_i$ 座城市。
- $2 \leq N \leq 2 \times 10^ 5$
- $1 \leq M \leq \min(5 \times 10^ 5, \frac{N(N - 1)}{2})$
- $1 \leq x_i, y_i \leq N$
- 保證輸入的圖為一張無向簡單連通圖，亦即沒有自環也沒有重邊
Output Format
對於每組輸入，第一行請輸出一個正整數 $k$ 代表至少要添加幾條道路。
接下來 $M$ 行的第$i$行請輸出兩個正整數 $a_i, b_i$，代表將原圖第 $i$ 條道路 $(x_i, y_i)$ 重新定向為 $a_i \to b_i$。
接下來 $k$ 行的第 $i$ 行請輸出兩個正整數 $c_i, d_i$，代表新添加的一條單向道路 $c_i \to d_i$。
若有多種方案滿足最小化添加道路的條件，請任意輸出一種解即可。
Sample Input 1
3 2
1 2
1 3
1 2
1 3
Sample Output 1
1
1 2
3 1
2 3
1 2
3 1
2 3
Sample Input 2
4 4
1 2
1 3
2 4
1 4
1 2
1 3
2 4
1 4
Sample Output 2
1
1 2
3 1
2 4
4 1
4 3
1 2
3 1
2 4
4 1
4 3
Hints
Problem Source
IOICamp 2020 Day3 pJ
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~49 | 無額外限制 | 100 |