回顧用嚟計算無向圖入面嘅割點(又稱為關節點)嘅 Tarjan 演算法,佢嘅偽代碼如演算法 1 所示。
Algorithm 1 The Correct Tarjan Algorithm
1: function TARJAN(i, d)
2: visited[i] <- true
3: depth[i] <- d
4: low[i] <- d
5: childCount <- 0
6: isArticulation <- false
7:
8: for each j in adj[i] do
9: if j = parent[i] then
10: continue
11: end if
12: if not visited[j] then
13: parent[j] <- i
14: TARJAN(j, d + 1)
15: childCount <- childCount + 1
16: if low[j] >= depth[i] then
17: isArticulation <- true
18: end if
19: low[i] <- min(low[i], low[j])
20: else
21: low[i] <- min(low[i], depth[j])
22: end if
23: end for
24: if (parent[i] != null and isArticulation)
or (parent[i] = null and childCount > 1)
then
25: Output i as articulation point
26: end if
27: end function
Algorithm 2 The Incorrect Trajan Algorithm
1: function TRAJAN(i, d)
2: visited[i] <- true
3: depth[i] <- d
4: low[i] <- d
5: childCount <- 0
6: isArticulation <- false
7:
8: for each j in adj[i] do
9: if j = parent[i] then
10: continue
11: end if
12: if not visited[j] then
13: parent[j] <- i
14: TRAJAN(j, d + 1)
15: childCount <- childCount + 1
16: if low[j] >= depth[i] then
17: isArticulation <- true
18: end if
19: end if
20: low[i] <- min(low[i], low[j])
21:
22:
23: end for
24: if (parent[i] != null and isArticulation)
or (parent[i] = null and childCount > 1)
then
25: Output i as articulation point
26: end if
27: end function
請注意,喺偽代碼入面,$\textit{adj}[i]$ 係包含所有與頂點 $i$ 相鄰嘅頂點嘅數組,$\textit{parent}$ 係每個元素初始值都係 $\text{null}$ 嘅數組,而 $\textit{visited}$ 係每個元素初始值都係 $\text{false}$ 嘅數組。
有啲學生可能好難理解呢個演算法,特別係第 $19$ 行到第 $22$ 行。佢哋唔明點解 Tarjan 演算法 需要用唔同嘅方式去計算 $\textit{low}[i]$ 嘅值,因此可能會喺腦海入面記住咗一個錯誤版本嘅演算法。我哋將呢個錯誤版本嘅演算法稱為 Trajan 演算法,如演算法 2 所示。注意 Tarjan 同 Trajan 演算法除咗函數名稱同埋第 $19$ 行到第 $22$ 行嘅 $4$ 行之外,幾乎完全一樣。
畀定一個有 $n$ 個頂點同 $m$ 條邊嘅無向連通圖,請對每個頂點 $u$ 判斷是否存在一個頂點 $v$ 同埋一個 $2$ 維數組 $\textit{adj}$($\textit{adj}$ 必須表示畀定嘅圖),使得 $\textsc{Tarjan}(v, 0)$ 同 $\textsc{Trajan}(v, 0)$ 喺頂點 $u$ 上面產生唔同嘅結果(即係話,Tarjan 演算法 判定頂點 $u$ 係割點而 Trajan 演算法 唔係,或者反過嚟)。
輸入格式
輸入包含多個測試用例。輸入嘅第一行包含一個整數 $T$ ($1 \le T \le 10^4$),表示測試用例嘅數量。對於每個測試用例:
第一行包含兩個整數 $n$ 同 $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$),表示畀定圖入面嘅頂點數同邊數。
接住落嚟嘅 $m$ 行,第 $i$ 行包含兩個整數 $u_i$ 同 $v_i$ ($1 \le u_i, v_i \le n$),表示圖入面有一條連接頂點 $u_i$ 同 $v_i$ 嘅邊。
保證畀定嘅圖係連通嘅,而且冇自環或者重邊。另外,所有測試用例嘅 $n$ 總和同 $m$ 總和都唔會超過 $10^6$。
輸出格式
對於每個測試用例,輸出一行,包含若干個由單個空格隔開並按遞增順序排列嘅整數。每個整數代表一個 Tarjan 同 Trajan 演算法可能會產生唔同結果嘅頂點。如果唔存在噉樣嘅頂點,請改為喺一行入面輸出 Empty。
樣例
樣例輸入 1
2 9 12 1 3 2 3 1 2 3 6 6 9 9 3 4 6 5 6 4 5 7 9 8 9 7 8 2 1 1 2
樣例輸出 1
3 6 9 Empty
說明
對於第一個樣例測試用例:
- 對於 $u = 3$,考慮 $v = 1$ 同埋 $\textit{adj} = [[3, 2], [3, 1], [1, 2, 6, 9], [6, 5], [6, 4], [4, 5, 3, 9], [9, 8], [9, 7], [7, 8, 3, 6]]$。
- 對於 $u = 6$,考慮 $v = 4$ 同埋 $\textit{adj} = [[2, 3], [1, 3], [9, 6, 2, 1], [6, 5], [6, 4], [4, 5, 3, 9], [9, 8], [9, 7], [7, 8, 3, 6]]$。
- 對於 $u = 9$,考慮 $v = 7$ 同埋 $\textit{adj} = [[2, 3], [1, 3], [9, 6, 2, 1], [5, 6], [4, 6], [9, 3, 5, 4], [9, 8], [9, 7], [7, 8, 3, 6]]$。
請注意,說明入面嘅所有 $\textit{adj}$ 都係由 $1$ 開始編號嘅。