В Байтляндии было решено провести голосование. Чтобы проголосовать человеку нужно подъехать в ближайший пункт голосования. Жители Байтляндии ленивы. Если путешествие от того места, где они живут, до пункта голосования занимает больше одного дня, на голосование они не пойдут. Байтляндия имеет вид неориентированного графа. Время путешествия по каждой из дорог - ровно один день. Вдоль каждой дороги страны живут люди (равномерно по дороге и очень густо). Пункты голосования можно строить только в вершинах. Соответственно, чтобы все проголосовали (т.е. пошли на голосование), нужно, чтобы у каждого ребра в одном из двух концов был пункт голосования.
Необходимо помочь правителю страны сэкономить деньги и выбрать минимальное по размеру множество вершин, в которых нужно соорудить пункты голосования.
На первой строке числа N и M - количество вершин и ребер графа соответственно (1 ≤ N ≤ 50000, 1 ≤ M ≤ 100000). Следующие M строк содержат по 2 числа - a и b (1 ≤ a, b, ≤ N, a ≠ b), что означает, что между городами a и b есть дорога.
Выходной файл должен состоять из двух строк - число вершин k на первой строке и k чисел от 1 до n на второй.
На реальном контесте оцивание происходило так:
Вы могли скачать входные тесты.
Оценивались выходные тесты, а не программа.
Если ваши k вершин не покрывают все m ребер, вы получите 0 баллов за тест. Если же ответ корректен, число баллов зависит от размера выбранного вами множества. Пусть ваш ответ = y, а оптимальный = b. Тогда вы заработаете 10·((8b-7y)/b)^2 баллов (округленное к ближайшему целому).
Мы решились пойти на эксперимент и на свой страх и риск оценить именно Вашу программу.