Problem
FOLGE X: FIRION SCHLÄGT ZURÜCK
Berland ist nach einer großen Niederlage im Krieg gegen Sterland endlich stärker geworden, und der Kaiser von Berland, Firion, bereitet einen Angriff auf den Feind vor.
Sterland ist eine bestimmte Anzahl von Städten, die durch bilaterale Straßen verbunden sind. Von jeder Stadt in Sterland kann man zu jeder anderen Stadt gelangen. Keine Straße verbindet die Stadt mit sich selbst.
Folgendes ist geplant:
Die Stadt, die angegriffen werden soll, wird ausgewählt. Die Stadt wird zerstört, und die Straßen, die von ihr ausgehen, werden barrikadiert. Dabei muss Sterland seine Integrität verlieren. Als nächstes wird einer der gebildeten Bereiche angegriffen. Dieser Bereich muss jedoch mindestens 1/8 und nicht mehr als 1/4
der verbleibenden Landesfläche betragen ( die Fläche wird in der Anzahl der Städte in diesem Gebiet gemessen). Wenn Sterland bei der Zerstörung einer Stadt unversehrt bleibt oder sich keine geeigneten Gebiete bilden, ist diese Stadt nicht für einen Angriff geeignet.
Firion möchte wissen, wie viele Städte die oben beschriebenen Bedingungen erfüllen, sowie die Zahlen dieser Städte in aufsteigender Reihenfolge.
Eingabe
Die erste Zeile enthält zwei Zahlen: n – Anzahl der Städte in Sterland ( 2 <= n <= 10^3), m – Anzahl der Straßen in Sterland ( 1 <= m <= 10^4).
Es folgen m Zeilen, in denen die Straßenbeschreibung angegeben wird, nämlich: Jede Zeile enthält zwei Zahlen: X und Y. Dies bedeutet, dass die Stadt X und die Stadt Y durch eine Straße verbunden sind.
Ausgabe
Geben Sie in der ersten Zeile die Anzahl der Städte aus, die für den Angriff geeignet sind. Geben Sie in der zweiten Zeile s von Zahlen aus - die Zahlen solcher Städte sind in aufsteigender Reihenfolge.
Beispiel
5 5
1 2
1 3
2 3
3 4
4 5 |
1
4 |