NTUCPC Speed Run! #1 比賽已結束，感謝大家的參與！題目連結
IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
136 . 找錢包
TopCoder
Tags
Description
雞塊所住的城市有 $N$ 個十字路口和 $M$ 條路，分別編號 $1$ 到 $N$ 和 $1$ 到 $M$，每條路都是可以雙向通行的。其中有 $K$ 條重要路，這些路是重要幹道，所以你可以從任何十字路口在只通過重要路的情況下走到剩下的所有十字路口。
某一天雞塊要搭高鐵去比賽的時候，發現他的隊友居然把錢包弄丟了！少了大腿隊友的話雞塊會什麼題目都寫不出來，所以雞塊必須去把他的錢包找出來。因為他的隊友只走大路，所以雞塊只需要把所有的重要路都走過就一定可以找到錢包。雞塊現在在 $1$ 號點的高鐵站，並且要走到 $N$ 號點的警察局找他的隊友。
在正要開始走的時候，雞塊不禁產生了一個問題：「是不是能夠在走過每條路不超過一次的前提下走過所有重要路呢？」因為雞塊的智商不足，所以他找上了全營隊的智商天花板，你。
Input Format
第一行有三個整數 $N, M, K$。
接下來有 $M$ 行，第 $i + 1$ 行有兩個數字 $u_i, v_i$，代表第 $i$ 條路連接著第 $u_i$ 和 $v_i$ 個路口。前 $K$ 條是重要路，剩下的 $M - K$ 條是正常路。
- $2 \le N \le 2 \times 10^ 5$
- $1 \le M \le 4 \times 10^ 5$
- $N - 1 \le K \le M$
- $1 \le u_i < v_i \le N$
- $(u_i, v_i) \neq (u_j, v_j)\ \forall i \neq j$
- 對所有十字路口 $u, v$，可以在只通過重要路的情況下從 $u$ 走到 $v$
Output Format
如果存在一條這樣的路，輸出 Yes，否則輸出 No。
Sample Input 1
4 4 4
1 2
1 3
2 3
1 4
1 2
1 3
2 3
1 4
Sample Output 1
Yes
Sample Input 2
5 8 5
1 2
2 3
3 4
4 5
3 5
1 4
1 3
1 5
1 2
2 3
3 4
4 5
3 5
1 4
1 3
1 5
Sample Output 2
Yes
Sample Input 3
5 4 4
1 2
2 3
2 4
1 5
1 2
2 3
2 4
1 5
Sample Output 3
No
Hints
Problem Source
IOICamp 2023 Day5 pK
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測資 | 0 |
| 2 | 0, 2~23 | $K = M$ | 30 |
| 3 | 0~36 | 無其他限制 | 70 |