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