EduBrick

J. Точки сочленения

3000 мс · 256 МБ · всё или ничего

Точка сочленения — вершина, при удалении которой (вместе с её рёбрами) число компонент связности растёт. Найдите все точки сочленения.

Считается тем же обходом и той же функцией подъёма, что и мосты, но условие другое и делится на два случая.

Не корень. Вершина pp — точка сочленения, если у неё есть сын vv с low[v]≥tin[p]low[v] \ge tin[p]. Разница с мостом ровно в знаке: у моста строгое неравенство. Нестрогое означает «из поддерева сына можно подняться максимум до самой pp, но не выше» — то есть без pp поддерево отваливается.

Корень. Корень обхода — точка сочленения тогда и только тогда, когда у него больше одного сына в дереве обхода. Функция подъёма тут ни при чём, и это отдельный случай, который забывают чаще всего.

Петли и кратные рёбра на ответ не влияют: ни то, ни другое не может отделить часть графа.

Формат ввода

Первая строка содержит числа nn (1≤n≤2⋅1041 \le n \le 2 \cdot 10^4) и mm (0≤m≤2⋅1050 \le m \le 2 \cdot 10^5).

Далее идут mm строк с рёбрами. Граф не обязан быть связным; возможны кратные рёбра и петли.

Формат вывода

В первой строке — количество точек сочленения.

Во второй — их номера по возрастанию. Если их нет, вторая строка пустая.

Примеры

ввод
6 7
1 2
2 3
3 4
1 3
4 5
4 6
5 6
вывод
2
3 4
ввод
3 2
1 2
2 3
вывод
1
2
Войдите, чтобы отправлять решения.