Douches au Japon – Regional event 2008

Level 6

ENONCE

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.

SORTIE

un entier, 1 si tout le monde peut prendre sa douche en même temps, et 0 sinon.

Runtime constraints

Maximum memory usage
2000 kilobytes
Maximum execution time
2000 milliseconds

Input/output samples

Sample input
6 7
0 1
1 2
2 3
3 4
4 5
5 0
1 4
Sample output
1
Sample input
6 5
0 1
1 2
3 4
4 5
5 3
Sample output
0

Submit your solution

You have to register or log in to be able to submit your solution.