În GInfoLand sunt mai multe orașe în care există un număr total de N intersecții. Între acestea sunt un număr total de M străzi. Oricare două străzi se pot intersecta doar în una dintre cele N intersecții și doar la extremități.
Pentru ca străzile să fie supravegheate au fost angajați exact N / 2 polițiști (N este număr par) și fiecare este responsabil pentru exact două străzi. Pentru a putea supraveghea cele două străzi, polițistul trebuie să stea într-o intersecție în care cele două străzi se întâlnesc.
Va trebui să determinați dacă este posibil ca cele N străzi să fie supravegheate în aceste condiții.
Datele de intrare se citesc de la intrarea standard. Pe prima linie se află două numere întregi, separate printr-un spațiu, reprezentând numărul total al intersecțiilor, respectiv numărul total al străzilor. Fiecare dintre următoarele M linii conține două numere întregi diferite, separate printr-un spațiu, reprezentând numerele de ordine a două intersecții care delimitează o stradă. Vor exista întotdeauna cel puțin două străzi și cel mult 1.000.000 de străzi, iar numărul străzilor va fi par. Intersecțiile sunt numerotate de la 1 la N. Între două intersecții se poate afla cel mult o stradă. Într-o intersecție se pot afla mai mulți polițiști, dar ei trebuie să supravegheze străzi diferite.
Datele de ieșire se scriu la ieșirea standard. Se va scrie o singură linie pe care se va afla cuvântul DA în cazul în care supravegherea este posibilă sau cuvântul NU în cazul în care supravegherea nu este posibilă.
Exemple
Intrare
|
1 2 3 4 5 6 7 8 9 10 11 |
8 10 1 2 1 3 1 4 2 3 2 4 3 4 5 6 5 8 6 7 7 8 |
Ieșire
|
1 |
DA |
Intrare
|
1 2 3 4 5 6 7 8 9 |
7 8 1 2 2 3 3 4 1 3 2 4 5 6 5 7 6 7 |
Ieșire
|
1 |
NU |
