1446 . 找輪子
TopCoder
Tags
Description
世界上的輪子跟門到底哪個比較多？我們可以把這東西想成一個圖論問題。
定義一個「輪子」是一個簡單環以及一個軸心節點組成，並且簡單環上的各個節點跟軸心之間都有一條邊。
比如說，左圖就是一個輪子，而右圖則不是。
今天的問題就是，給一張簡單連通圖，請問他存不存在一個子圖是一個輪子。
也就是說，在這張圖上找不找得到一個邊跟點的子集使得該子集形成的圖是一個輪子。
Input Format
輸入第一行有兩個正整數 $n, m$，代表圖的點跟邊的數量。
第二行開始輸入 $m$ 行，每行有兩個整數 $u_i, v_i$ 表示圖上 $u_i, v_i$ 之間有一條邊。
- $1 \leq n, m \leq 2 \times 10 ^ 5$
- $1 \leq u_i, v_i \leq n$
- 保證這張圖是簡單連通圖（也就是沒有重邊跟自環）
Output Format
如果這張圖有輪子，則在第一行輸出 Yes ，否則在第一行輸出 No。
如果這張圖有輪子，則
- 在第二行輸出兩個整數 $k, s$ ，表示這個輪子的軸心為 $s$ ，且外圍有 $k-1$ 個節點（也就是說，總共有 $k$ 個節點）。
- 在第三行輸出 $k - 1$ 個相異的整數 $a_1 \dots a_{k-1}$ 表示外圍的節點，滿足 $a_i, a_{(i \bmod (k-1)) + 1}$ 之間有一條邊，且 $a_i, s$ 之間有一條邊。
Sample Input 1
6 10 1 2 1 3 1 4 1 5 1 6 2 3 3 4 4 5 5 6 6 2
Sample Output 1
Yes 6 1 6 5 4 3 2
Sample Input 2
6 8 1 2 1 3 1 4 1 5 1 6 2 3 3 4 4 5
Sample Output 2
No
Hints
注意簡單環的定義是一個長度至少 3 的閉合路徑，中途不重複經過任何頂點。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資。 | 0 |
| 2 | 0~29 | $n \leq 500$ | 30 |
| 3 | 0~51 | 無特別限制 | 70 |