Problema lunii: supraveghere

Î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

Ieșire

Intrare

Ieșire

Te-ar putea interesa și:

  • Adrian Pop-Tifrea

    Trebuie supravegheate cele N intersectii sau cele M strazi ?

    • Petruta George-Calin

      "Va trebui să determinați dacă este posibil ca cele N străzi să fie supravegheate în aceste condiții."