* $1 ≤ M ≤ 200.000$
* Este posibil ca unele dintre cele $M$ drumuri de la $a$ la $b$ să aibă $a = b$, aşa cum numai într-un sistem de drumuri oltenesc mai vezi. De asemenea, pentru unele perechi $(a, b)$ este posibil să fie mai multe drumuri de la $a$ la $b$.
* Observaţi că traseul lui Nea Mărin poate trece de mai multe ori prin acelaşi nod (vezi exemple).

* Pentru 15 puncte, N ≤ 8, M ≤ 22
* Pentru alte (17 puncte): N ≤ 600, M ≤ 3.000
* Pentru alte (19 puncte): Se garantează că pentru oricare 51 de oraşe distincte alese dintre cele N, există printre acestea două oraşe a şi b, cu proprietatea următoare: dacă există un traseu de la a la b (indiferent de tipul de drumuri care îl compun) atunci nu exista un traseu de la b la a.
* Pentru alte 20 puncte): Sunt exact N drumuri naţionale, acestea fiind 1→2, 2→3, ..., (N-1)→N şi N→1.
* Pentru alte 29 puncte): Fără restricţii suplimentare.

* Pentru $15$ puncte, $N ≤ 8, M ≤ 22$
* Pentru alte $17$ puncte $N ≤ 600, M ≤ 3.000$
* Pentru alte $19$ puncte se garantează că pentru oricare $51$ de oraşe distincte alese dintre cele $N$, există printre acestea două oraşe $a$ şi $b$, cu proprietatea următoare: dacă există un traseu de la $a$ la $b$ (indiferent de tipul de drumuri care îl compun) atunci nu exista un traseu de la $b$ la $a$.
* Pentru alte $20$ puncte sunt exact N drumuri naţionale, acestea fiind de la $1$ la $2$, de la $2$ la $3$, ..., de la $N-1$ la $N$ şi de la $N$ la $1$.

h2. Exemple

Intrare Ieşire Explicaţii
3 3

 
table(example). |_. semafor2.in |_. semafor2.out |_. Explicaţie |_. Diagrama |
| 3 3

1 2 0
2 3 1
3 1 1

000 Exista un singur traseu 1->2->3->1.

| 000
|Exista un singur traseu 1->2->3->1.

Indiferent din ce oraş ar începe Nea
Marin traseul, acesta nu ar fi
echilibrat, fiind format din doua
drumuri naţionale şi o poteca.

2 3

| !problema/semafor2?1.png!
|
|2 3

1 2 0
2 1 1
2 2 1

11 Nea Marin poate parcurge traseul

| 11
|Nea Marin poate parcurge traseul

1->2->1, care este atât echilibrat,
cât şi nemonoton, indiferent dacă
este început din oraşul 1 sau din
oraşul 2.

7 9

| !problema/semafor2?2.png!
|
| 7 9

1 2 0
2 6 1
4 2 1

3 5 1
2 7 0
7 1 1

1101011 Nea Marin poate parcurge

|1101011
| Nea Marin poate parcurge

traseul 1->2->6->4->2->7
->1, care este atât
echilibrat, cât şi

observă că răspunsul este
0, deoarece nu exista
poteci ce le au ca sursa.

Limită de timp: 0.6 secunde
Memorie totală: 256 MB
Poveste şi cerinţă...
 
h2. Date de intrare
 
Fişierul de intrare $semafor2.in$ ...
 
h2. Date de ieşire
 
În fişierul de ieşire $semafor2.out$ ...
 
h2. Restricţii
 
* $... ≤ ... ≤ ...$
 
h2. Exemplu
 
table(example). |_. semafor2.in |_. semafor2.out | Explicaţie |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| !problema/semafor2?3.png!

|
== include(page="template/taskfooter" task_id="semafor2") ==