무방향 그래프에서 단절점(articulation point 또는 cut vertex)을 구하는 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$에 대해 $\textsc{Tarjan}(v, 0)$과 $\textsc{Trajan}(v, 0)$이 정점 $u$에서 서로 다른 결과를 내도록 하는 정점 $v$와 $2$차원 배열 $\textit{adj}$($\textit{adj}$는 주어진 그래프를 나타내야 함)가 존재하는지 판별하십시오(즉, 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$를 잇는 간선이 있음을 나타내는 두 정수 $u_i$와 $v_i$ ($1 \le u_i, v_i \le n$)가 주어집니다.
주어진 그래프는 연결 그래프이며 자기 루프나 다중 간선이 없음이 보장됩니다. 또한 모든 테스트 케이스에서 $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$-인덱스($1$-indexed) 기준임에 유의하십시오.