eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач

Article

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

В 2048 году социологи заинтересовались структурой сообщества олимпиадников-алгоритмистов и в результате своих исследований сделали следующие наблюдения. Новость о успехах любого олимпиадника может распространиться от любого из его знакомых ко всем его знакомым, при том, что любые два человека не общаются, если они не знакомы, и обсуждают только успехи своих общих знакомых. Кроме того, у каждого среди его знакомых нету троих, попарно друг с другом не знакомых.

И вот сообщество решило приобрести в складчину безумно дорогую статью о новом алгоритме умножения квадратных матриц, работающем за время Θ(N^{2,32768}), где N — порядок матриц. Делать копии статьи строжайше запрещено законами. При этом каждый хочет прочитать статью, но не готов отдавать её незнакомому человеку. К тому же, никому не хочется возиться со статьёй после прочтения. Кроме Васи — хранителя статьи, которому поручена её покупка и у которого статья будет храниться впоследствии. Но Вася тоже готов только купить статью, прочитать, передать дальше и забрать статью у последнего прочитавшего, но не передавать от одного человека другому.

Требуется определить наибольшее количество человек, которые смогут прочитать статью и схему передачи статьи от одного человека другому.

Входные данные

Граф до 1000 вершин и до 10000 рёбер.

Выходные данные

Наибольшее количество и порядок, в котором люди получат статью.

Пример

Входные данные #1
3 3
1 2
1 3
2 3
Выходные данные #1
3
1 3 2 
Источник NEERC Western Subregional Contest 2012