Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Difficulty: [show] Hackable ✓
Statistics

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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.