Problem
EPISÓDIOX: FIRION CONTRA-ATACA
Berland finalmente ficou mais forte após uma grande derrota na guerra contra Sterland, e o Imperador de Berland Firion está preparando um ataque ao inimigo.
Sterland é um certo número de cidades conectadas por estradas de mão dupla. De qualquer cidade de Sterland você pode chegar a qualquer outra. Nenhuma estrada liga a cidade a ela mesma.
Está previsto o seguinte:
A cidade a ser atacada é selecionada. A cidade está destruída e as estradas que dela saem estão bloqueadas. Ao mesmo tempo, Sterland deve perder sua integridade. Em seguida, uma das áreas formadas é atacada. Nesse caso, essa área deve ser de pelo menos 1/8 e não mais que 1/4 & nbsp;
do restante área do país (a área é medida pelo número de cidades em uma determinada área). Se Sterland permanecer intacto quando uma cidade for destruída, ou nenhuma área adequada for formada, então esta cidade não é adequada para ataque.
Firion quer saber quantas cidades atendem às condições acima e o número dessas cidades em ordem crescente.
Entrada
A primeira linha contém dois números: n – número de cidades em Sterland ( 2 <= n <= 10^3), m – número de estradas em Sterland ( 1 <= m <= 10^4).
Em seguida, existem m linhas contendo a descrição das estradas, a saber: cada linha contém dois números: X e Y. Isso significa que a cidade X e a cidade Y estão conectadas por uma estrada.
Impressão
Na primeira linha imprima o número s – número de cidades adequadas para o ataque. Na segunda linha, imprima os números - números de tais cidades em ordem crescente.
Exemplo
5 5
1 2
1 3
23
34
4 5 |
1
4 |