Erinnern wir uns an den Tarjan-Algorithmus zur Berechnung der Artikulationspunkte (auch Schnittknoten genannt) in einem ungerichteten Graphen, dessen Pseudocode in Algorithmus 1 dargestellt ist.
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
Beachte, dass im Pseudocode $\textit{adj}[i]$ das Array ist, das alle zu Knoten $i$ benachbarten Knoten enthält, $\textit{parent}$ ein Array ist, in dem der Anfangswert jedes Elements $\text{null}$ ist, und $\textit{visited}$ ein Array ist, in dem der Anfangswert jedes Elements $\text{false}$ ist.
Einige Studierende haben Schwierigkeiten, diesen Algorithmus zu verstehen, insbesondere von Zeile $19$ bis Zeile $22$. Sie verstehen nicht, warum der Tarjan-Algorithmus den Wert von $\textit{low}[i]$ unterschiedlich berechnen muss, und merken sich möglicherweise eine falsche Version des Algorithmus. Nennen wir diese falsche Version den Trajan-Algorithmus, der in Algorithmus 2 dargestellt ist. Beachte, dass der Tarjan- und der Trajan-Algorithmus bis auf die Funktionsnamen und die $4$ Zeilen von Zeile $19$ bis Zeile $22$ fast identisch sind.
Gegeben ist ein ungerichteter zusammenhängender Graph mit $n$ Knoten und $m$ Kanten. Bestimme für jeden Knoten $u$, ob es einen Knoten $v$ und ein $2$-dimensionales Array $\textit{adj}$ gibt ($\textit{adj}$ muss den gegebenen Graphen darstellen), sodass $\textsc{Tarjan}(v, 0)$ und $\textsc{Trajan}(v, 0)$ für den Knoten $u$ unterschiedliche Ergebnisse liefern (das heißt, der Tarjan-Algorithmus gibt an, dass Knoten $u$ ein Artikulationspunkt ist, während der Trajan-Algorithmus dies nicht tut, oder umgekehrt).
Eingabe
Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine ganze Zahl $T$ ($1 \le T \le 10^4$), die die Anzahl der Testfälle angibt. Für jeden Testfall gilt:
Die erste Zeile enthält zwei ganze Zahlen $n$ und $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$), die die Anzahl der Knoten und Kanten im gegebenen Graphen angeben.
In den folgenden $m$ Zeilen enthält die $i$-te Zeile zwei ganze Zahlen $u_i$ und $v_i$ ($1 \le u_i, v_i \le n$), was bedeutet, dass es im Graphen eine Kante zwischen den Knoten $u_i$ und $v_i$ gibt.
Es wird garantiert, dass der gegebene Graph zusammenhängend ist und weder Selbstschleifen noch Mehrfachkanten enthält. Außerdem überschreiten weder die Summe von $n$ noch die Summe von $m$ über alle Testfälle hinweg $10^6$.
Ausgabe
Gib für jeden Testfall eine Zeile mit einigen durch jeweils ein Leerzeichen getrennten ganzen Zahlen in aufsteigender Reihenfolge aus. Jede ganze Zahl ist ein Knoten, bei dem der Tarjan- und der Trajan-Algorithmus unterschiedliche Ergebnisse liefern können. Falls es keine solchen Knoten gibt, gib stattdessen in einer Zeile Empty aus.
Beispiel
Beispieleingabe 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
Beispielausgabe 1
3 6 9 Empty
Hinweis
Für den ersten Beispieltestfall:
- Betrachte für $u = 3$ die Wahl $v = 1$ und $\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]]$.
- Betrachte für $u = 6$ die Wahl $v = 4$ und $\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]]$.
- Betrachte für $u = 9$ die Wahl $v = 7$ und $\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]]$.
Beachte, dass alle $\textit{adj}$ in der Erklärung $1$-indiziert sind.