eolymp
bolt
Try our new interface for solving problems
Məsələlər

Голосование

Голосование

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

В Байтляндии было решено провести голосование. Чтобы проголосовать человеку нужно подъехать в ближайший пункт голосования. Жители Байтляндии ленивы. Если путешествие от того места, где они живут, до пункта голосования занимает больше одного дня, на голосование они не пойдут. Байтляндия имеет вид неориентированного графа. Время путешествия по каждой из дорог - ровно один день. Вдоль каждой дороги страны живут люди (равномерно по дороге и очень густо). Пункты голосования можно строить только в вершинах. Соответственно, чтобы все проголосовали (т.е. пошли на голосование), нужно, чтобы у каждого ребра в одном из двух концов был пункт голосования.

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

Giriş verilənləri

На первой строке числа N и M - количество вершин и ребер графа соответственно (1N50000, 1M100000). Следующие M строк содержат по 2 числа - a и b (1a, b, ≤ N, ab), что означает, что между городами a и b есть дорога.

Çıxış verilənləri

Выходной файл должен состоять из двух строк - число вершин k на первой строке и k чисел от 1 до n на второй.

Nümunə

Giriş verilənləri #1
4 4
1 2
2 3
3 1
1 4
Çıxış verilənləri #1
2
1 3

Qeyd

На реальном контесте оцивание происходило так:

  1. Вы могли скачать входные тесты.

  2. Оценивались выходные тесты, а не программа.

  3. Если ваши k вершин не покрывают все m ребер, вы получите 0 баллов за тест. Если же ответ корректен, число баллов зависит от размера выбранного вами множества. Пусть ваш ответ = y, а оптимальный = b. Тогда вы заработаете 10·((8b-7y)/b)^2 баллов (округленное к ближайшему целому).

Мы решились пойти на эксперимент и на свой страх и риск оценить именно Вашу программу.