Вспомним алгоритм Тарьяна для поиска точек сочленения (также называемых шарнирами) в неориентированном графе, псевдокод которого приведён в Алгоритме 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$. Они не могут понять, почему алгоритм Тарьяна должен по-разному вычислять значение $\textit{low}[i]$, и могут запомнить неверную версию алгоритма. Назовём эту неверную версию алгоритмом Траяна, который приведён в Алгоритме 2. Заметим, что алгоритмы Тарьяна и Траяна почти одинаковы, за исключением названий функций и $4$ строк со строки $19$ по строку $22$.
Дан неориентированный связный граф с $n$ вершинами и $m$ рёбрами. Для каждой вершины $u$ определите, существуют ли вершина $v$ и $2$-мерный массив $\textit{adj}$ ($\textit{adj}$ должен задавать данный граф), такие что $\textsc{Tarjan}(v, 0)$ и $\textsc{Trajan}(v, 0)$ дают разные результаты для вершины $u$ (то есть алгоритм Тарьяна объявляет вершину $u$ точкой сочленения, а алгоритм Траяна — нет, или наоборот).
Входные данные
Входные данные состоят из нескольких наборов входных данных. Первая строка содержит целое число $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$.
Выходные данные
Для каждого набора входных данных выведите одну строку, содержащую несколько целых чисел, разделённых одним пробелом, в порядке возрастания. Каждое число — это вершина, на которой алгоритмы Тарьяна и Траяна могут дать разный результат. Если таких вершин нет, выведите вместо этого в одной строке 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$.