Problem
ÉPISODEX : FIRION CONTRE ATTAQUE
Berland est enfin devenu plus fort après une défaite majeure dans la guerre contre Sterland, et l'empereur de Berland Firion prépare une attaque contre l'ennemi.
Sterland est un certain nombre de villes reliées par des routes à double sens. De n'importe quelle ville de Sterland, vous pouvez vous rendre dans n'importe quelle autre. Aucune route ne relie la ville à elle-même.
Il est prévu :
La ville à attaquer est sélectionnée. La ville est détruite et les routes qui en sortent sont barricadées. Dans le même temps, Sterland devrait perdre son intégrité. Ensuite, l'une des zones formées est attaquée. Dans ce cas, cette zone doit être d'au moins 1/8 et pas plus de 1/4 & nbsp;
de la superficie restante du pays (la superficie est mesurée en nombre de villes dans une zone donnée). Si Sterland reste intact lorsqu'une ville est détruite, ou si aucune zone appropriée n'est formée, alors cette ville ne peut pas être attaquée.
Firion veut savoir combien de villes remplissent les conditions ci-dessus, et le nombre de ces villes par ordre croissant.
Entrée
La première ligne contient deux nombres : n – nombre de villes de Sterland ( 2 <= n <= 10^3), m – nombre de routes à Sterland ( 1 <= m <= 10^4).
Ensuite, il y a m lignes contenant la description des routes, à savoir : chaque ligne contient deux nombres : X et Y. Cela signifie que la ville X et la ville Y sont reliées par une route.
Mentions légales
Sur la première ligne, écrivez le numéro s – nombre de villes pouvant être attaquées. Dans la deuxième ligne, écrivez les chiffres - numéros de ces villes par ordre croissant.
Exemple
5 5
1 2
1 3
23
34
4 5 |
1
4 |