Przypomnijmy algorytm Tarjana służący do wyznaczania punktów artykulacji (nazywanych również wierzchołkami rozspajającymi) w grafie nieskierowanym, którego pseudokod przedstawiono w Algorytmie 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
Zauważ, że w pseudokodzie $\textit{adj}[i]$ jest tablicą zawierającą wszystkie wierzchołki sąsiadujące z wierzchołkiem $i$, $\textit{parent}$ jest tablicą, w której wartością początkową każdego elementu jest $\text{null}$, natomiast $\textit{visited}$ jest tablicą, w której wartością początkową każdego elementu jest $\text{false}$.
Niektórzy studenci mogą mieć trudności ze zrozumieniem tego algorytmu, zwłaszcza od wiersza $19$ do wiersza $22$. Nie rozumieją oni, dlaczego algorytm Tarjana musi obliczać wartość $\textit{low}[i]$ w różny sposób, i mogą zapamiętać niepoprawną wersję algorytmu. Nazwijmy tę niepoprawną wersję algorytmem Trajana, przedstawionym w Algorytmie 2. Zwróć uwagę, że algorytmy Tarjana i Trajana są niemal identyczne, z wyjątkiem nazw funkcji oraz $4$ wierszy od wiersza $19$ do wiersza $22$.
Dla danego nieskierowanego grafu spójnego o $n$ wierzchołkach i $m$ krawędziach, dla każdego wierzchołka $u$ rozstrzygnij, czy istnieją wierzchołek $v$ oraz $2$-wymiarowa tablica $\textit{adj}$ ($\textit{adj}$ musi reprezentować dany graf) takie, że wywołania $\textsc{Tarjan}(v, 0)$ oraz $\textsc{Trajan}(v, 0)$ dają różne wyniki dla wierzchołka $u$ (to znaczy algorytm Tarjana uznaje wierzchołek $u$ za punkt artykulacji, podczas gdy algorytm Trajana nie, lub odwrotnie).
Wejście
Wejście zawiera wiele przypadków testowych. Pierwszy wiersz wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 10^4$) oznaczającą liczbę przypadków testowych. Dla każdego przypadku testowego:
Pierwszy wiersz zawiera dwie liczby całkowite $n$ oraz $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$) oznaczające liczbę wierzchołków i krawędzi w danym grafie.
W kolejnych $m$ wierszach $i$-ty wiersz zawiera dwie liczby całkowite $u_i$ oraz $v_i$ ($1 \le u_i, v_i \le n$) oznaczające, że w grafie istnieje krawędź łącząca wierzchołki $u_i$ oraz $v_i$.
Gwarantuje się, że dany graf jest spójny oraz nie zawiera pętli ani krawędzi wielokrotnych. Ponadto ani suma $n$, ani suma $m$ po wszystkich przypadkach testowych nie przekroczy $10^6$.
Wyjście
Dla każdego przypadku testowego wypisz jeden wiersz zawierający pewne liczby całkowite oddzielone pojedynczą spacją w porządku rosnącym. Każda liczba całkowita to wierzchołek, dla którego algorytmy Tarjana i Trajana mogą dać różne wyniki. Jeśli takie wierzchołki nie istnieją, wypisz zamiast tego w jednym wierszu Empty.
Przykład
Przykładowe wejście 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
Przykładowe wyjście 1
3 6 9 Empty
Uwaga
Dla pierwszego przykładowego przypadku testowego:
- Dla $u = 3$ rozważ $v = 1$ oraz $\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]]$.
- Dla $u = 6$ rozważ $v = 4$ oraz $\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]]$.
- Dla $u = 9$ rozważ $v = 7$ oraz $\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]]$.
Zauważ, że wszystkie tablice $\textit{adj}$ w wyjaśnieniu są indeksowane od $1$.