Problem
EPISODX: FIRION STRIKES BACK
Berland has finally grown stronger after a major defeat in the war against Sterland, and the Emperor of Berland Firion is preparing an attack on the enemy.
Sterland is a certain number of cities connected by two-way roads. From any city of Sterland you can get to any other. No road connects the city to itself.
The following is planned:
The city to be attacked is selected. The city is destroyed, and the roads emanating from it are barricaded. At the same time, Sterland should lose its integrity. Next, one of the formed areas is attacked. In this case, this area should be at least 1/8 and not more than 1/4 & nbsp;
from the remaining area of the country (the area is measured in the number of cities in a given area). If Sterland remains intact when a city is destroyed, or no suitable areas are formed, then this city is not suitable for attack.
Firion wants to know how many cities meet the above conditions, and the numbers of these cities in ascending order.
Input
The first line contains two numbers: n – number of cities in Sterland ( 2 <= n <= 10^3), m – number of roads in Sterland ( 1 <= m <= 10^4).
Then there are m lines containing the description of roads, namely: each line contains two numbers: X and Y. This means that city X and city Y are connected by a road.
Imprint
In the first line print the number s – number of cities suitable for attack. In the second line print s numbers - numbers of such cities in ascending order.
Example
5 5
1 2
1 3
23
34
4 5 |
1
4 |