DIFFICULTE
LIMITE DE MEMOIRE
2000 ko
LIMITE DE TEMPS
2000 ms
Après une dure année de travail, Joseph Marchand fait un voyage organisé au Japon ! Seulement, il est sous le choc quand il s'aperçoit que les douches sont collectives. Comme son groupe de français est très pudique, personne ne veut prendre sa douche dans une pièce où il y a quelqu'un qu'il connait. Notez qu'il y a 2 salles de douche différentes, et qu'on vous donne en entrée la liste des gens qui se connaissent. Pour simplifier, on dira que toutes les personnes du groupe de Joseph Marchand sont de sexe masculin, et que les 2 salles de douche sont réservées aux hommes.
Ecrivez un programme qui dit si il existe une assignation possible de chaque personne du groupe aux douches de telle façon qu'ils puissent la prendre tous en même temps, et qu'il n'y ait pas deux personnes qui se connaissent dans la même salle.
ENTREE- sur la première ligne, deux entiers N et M, séparés par un espace, indiquant respectivement le nombre de personnes dans le groupe de Joseph Marchand (1 <= N <= 1000), et le nombre de relations entre deux personnes (0 <= M <= 100000)
- sur les M lignes suivantes, deux entiers a et b, indiquant que la personne numéro a connait la personne numéro b. Les personnes seront numérotées de 0 à N-1. Il n'y aura pas de répétition dans cette liste. La relation de "connaissance" est symétrique : si a et b se connaissent, b et a se connaissent également.
SORTIEun entier, 1 si tout le monde peut prendre sa douche en même temps, et 0 sinon.
EXEMPLE(S) D'ENTREE/SORTIE
Exemple 1
en entrée ...
6 7 0 1 1 2 2 3 3 4 4 5 5 0 1 4 |
1 |
Exemple 2
en entrée ...
6 5 0 1 1 2 3 4 4 5 5 3 |
0 |
