Я заметил, что довольно часто большие дружные компании держатся на самом деле всего на нескольких людях. Если убрать такого человека (например, если он уезжает куда-то далеко или умирает), то большая компания сразу же распадается на несколько дружных групп поменьше. Я не слишком много понимаю в человеческих отношениях, но думаю, что понимаю, почему так происходит.
На самом деле, два человека общаются между собой, если у них в достаточной мере совпадают интересы. Будем называть таких двух людей настоящими друзьями. Если же этого не происходит, то они могут оставаться в дружеских отношениях просто потому, что у них имеется общий настоящий друг или у одного из них есть настоящий друг, у которого есть настоящий друг и тот, в свою очередь, настоящий друг другого. Тогда если между такими друзьями больше не останется настоящих друзей, то они более не станут дружить друг с другом. Так и распадаются большие дружные группы.
Будем называть человека душой компании, если его удаление из компании ведёт к её распаду на более мелкие группы. Напомню, что компания остаётся единой, если любые два человека в ней являются друзьями, хотя бы даже и не настоящими. В этой задаче вам нужно найти в компании из $$$n$$$ человек с известными парами настоящих друзей все души этой компании. Чтобы было проще, вместо имён у людей будут номера.
Одинокий Автор
P. S. Надеюсь, не слишком сумбурно.
В первой строке входного файла содержатся два целых числа: $$$n$$$ и $$$m$$$ ($$$2 \le n \le 10^4, 1 \le m \le 10^5$$$) — количество друзей в компании и количество пар настоящих друзей. Далее в $$$m$$$ строках содержатся пары целых чисел через пробел: $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$) — пары настоящих друзей. Гарантируется, что компания действительно дружная и что никакая пара настоящих друзей не повторяется дважды.
В первой строке входного файла должно быть записано единственное целое число — количество душ компании. Далее во второй строке через пробел должны быть перечислены номера людей, являющихся душами компании, в возрастающем порядке.
5 6 1 3 1 5 2 4 2 5 3 5 4 5
1 5
10 11 1 2 1 3 2 4 3 4 4 5 4 6 5 7 6 7 4 9 8 9 9 10
2 4 9
Во втором примере, удаление как четвёртого, так и девятого человека приводит к распаду компании на три группы.
