J. Точки сочленения
Точка сочленения — вершина, при удалении которой (вместе с её рёбрами) число компонент связности растёт. Найдите все точки сочленения.
Считается тем же обходом и той же функцией подъёма, что и мосты, но условие другое и делится на два случая.
Не корень. Вершина — точка сочленения, если у неё есть сын с . Разница с мостом ровно в знаке: у моста строгое неравенство. Нестрогое означает «из поддерева сына можно подняться максимум до самой , но не выше» — то есть без поддерево отваливается.
Корень. Корень обхода — точка сочленения тогда и только тогда, когда у него больше одного сына в дереве обхода. Функция подъёма тут ни при чём, и это отдельный случай, который забывают чаще всего.
Петли и кратные рёбра на ответ не влияют: ни то, ни другое не может отделить часть графа.
Формат ввода
Первая строка содержит числа () и ().
Далее идут строк с рёбрами. Граф не обязан быть связным; возможны кратные рёбра и петли.
Формат вывода
В первой строке — количество точек сочленения.
Во второй — их номера по возрастанию. Если их нет, вторая строка пустая.
Примеры
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