Пригадаємо алгоритм Тар'яна для знаходження точок зчленування (які також називають шарнірами) в неорієнтованому графі, псевдокод якого наведено в Алгоритмі 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$.