Problem
에피소드X: FIRION의 역습
Berland는 Sterland와의 전쟁에서 대패한 후 마침내 더 강해졌고, Berland의 황제 Firion은 적에 대한 공격을 준비하고 있습니다.
Sterland는 양방향 도로로 연결된 일정 수의 도시입니다. Sterland의 모든 도시에서 다른 도시로 이동할 수 있습니다. 어떤 도로도 도시 자체를 연결하지 않습니다.
다음이 예정되어 있습니다.
공격할 도시가 선택됩니다. 도시는 파괴되고 도시에서 나오는 도로는 바리케이드됩니다. 동시에 Sterland는 무결성을 잃어야 합니다. 다음으로 형성된 영역 중 하나를 공격합니다. 이 경우 이 면적은 1/8 이상 1/4 이하이어야 합니다 & nbsp; 국가의
나머지 지역(이 지역은 해당 지역의 도시 수로 측정됨). 도시가 파괴되었을 때 Sterland가 그대로 남아 있거나 적절한 지역이 형성되지 않았다면 이 도시는 공격하기에 적합하지 않습니다.
Firion은 위의 조건을 충족하는 도시의 수와 이러한 도시의 수를 오름차순으로 알고 싶어합니다.
입력
첫 번째 줄에는 두 개의 숫자가 포함됩니다. n – Sterland의 도시 수( 2 <= n <= 10^3), m – Sterland의 도로 수( 1 <= m <= 10^4).
그런 다음 도로에 대한 설명을 포함하는 m행이 있습니다. 즉, 각 행에는 X와 Y라는 두 개의 숫자가 있습니다. 이는 도시 X와 도시 Y가 도로로 연결되어 있음을 의미합니다.
출판물
첫 번째 줄에 숫자 s – 공격에 적합한 도시의 수. 두 번째 줄에 s 숫자를 인쇄합니다 - 오름차순의 도시 수.
예
<몸>
5 5
1 2
1 3
23
34
4 5 |
1
4 |