== include(page="template/taskheader" task_id="atena") ==
Poveste şi cerinţă...
În Grecia antică, reţeaua stradală a oricărui oraş era formată din intersecţii legate prin drumuri bidirecţionale, construite în aşa fel încât din orice intersecţie să se poată ajunge în oricare altă intersecţie, direct sau indirect, trecând prin alte intersecţii. De asemenea, între oricare două intersecţii ale unui oraş exista cel mult un drum direct şi nu existau drumuri de la o intersecţie la ea însăşi.
Se ştie că în acele vremuri, reţeaua stradală a oraşului Atena avea $N{~1~}$ intersecţii, legate prin $M{~1~}$ drumuri bidirecţionale, în timp ce reţeaua stradală a oraşului Sparta avea $N{~2~}$ intersecţii, legate prin $M{~2~}$ drumuri bidirecţionale. Intersecţiile din Atena se consideră numerotate cu numere de la $1$ la $N{~1~}$, în timp ce intersecţiile din Sparta se consideră numerotate cu numere de la $N{~1~} + 1$ la $N{~1~} + N{~2~}$.
Pericle, regele Atenei, a decis să afle în ce măsură reţeaua de străzi a Spartei este asemănătoare cu reţeaua de străzi a oraşului Atena. În acest scop, el i-a cerut unuia dintre matematicienii atenieni, Parmenide, să afle dacă reţeaua de străzi a Spartei este inclusă în reţeaua de străzi a Atenei.
Pericle consideră că reţeaua de străzi a Spartei este inclusă în reţeaua de străzi a Atenei dacă şi numai dacă există submulţimi disjuncte două câte două nevide $A{~1~}, A{~2~}, ..., A{~N{~2~}~}$ ale mulţimii ${ 1, 2, ..., N{~1~} }$ cu proprietatea că pentru orice drum între două intersecţii $N{~1~} + a$ şi $N{~1~} + b$ în Sparta există un drum între o intersecţie $c$ şi o intersecţie $d$ în Atena, cu $c$ din $A{~a~}$, $d$ din $A{~b~}$ şi $1 <= a, b <= N{~2~}$, $1 <= c, d <= N{~1~}$.
Din păcate Parmenide a murit în timp ce încerca să ajungă la Congresul de Matematică Aplicată din Siracuza, aşa că sarcina lui v-a revenit vouă. Totuşi Parmenide a menţionat în treacăt înainte să plece că rezolvarea problemei se bazează în mod esenţial pe următoarele două proprietăţi ale reţelei stradale din Atena:
* $N{~1~} ≥ 2 * M{~2~}$;
* Oricum am alege o intersecţie $a$ din Atena şi alte $3$ intersecţii distincte $b$, $c$ şi $d$ legate prin drumuri directe de $a$, există un drum direct între $b$ şi $c$ sau între $c$ şi $d$ sau între $b$ şi $d$ (pot exista şi două dintre aceste drumuri directe sau chiar toate trei la un loc).
Scrieţi un program care determină dacă reţeaua stradală din Sparta este inclusă în reţeaua stradală din Atena, în sensul dat de Pericle. Dacă răspunsul este afirmativ, atunci programul trebuie să determine şi mulţimile $A{~1~}, A{~2~}, ..., A{~N{~2~}~}$.
h2. Date de intrare
Fişierul de intrare $atena.in$ ...
Fişierul de intrare $atena.in$ are următoarea structură:
* pe prima linie se află două numere naturale $N{~1~}$ şi $M{~1~}$, reprezentând numărul de intersecţii din Atena, respectiv numărul de drumuri bidirecţionale dintre ele;
* pe fiecare din următoarele $M{~1~}$ linii sunt scrise două numere naturale separate printr-un spaţiu $x y (1 ≤ x, y ≤ N{~1~}$) cu semnificaţia că între intersecţiile $x$ şi $y$ din Atena exista drum;
* pe următoarea linie se află două numere naturale $N{~2~}$ şi $M{~2~}$, reprezentând numărul de intersecţii din Sparta, respectiv numărul de drumuri bidirecţionale dintre ele;
* pe fiecare din următoarele $M{~2~}$ linii sunt scrise două numere naturale separate printr-un spaţiu $x y (N{~1~} + 1 ≤ x, y ≤ N{~1~} + N{~2~})$ cu semnificaţia că între intersecţiile $x$ şi $y$ din Sparta exista drum.
h2. Date de ieşire
În fişierul de ieşire $atena.out$ ...
În fişierul de ieşire $atena.out$ se va găsi pe prima linie cuvântul $DA$ dacă reţeaua stradală din Sparta este inclusă în reţeaua stradală din Atena sau $NU$ dacă nu este inclusă.
Numai în cazul în care pe prima linie se află $DA$ trebuie să urmeze $N{~2~}$ linii cu următoarea structură:
* pe linia $i + 1 (1 ≤ i ≤ N{~2~})$ se vor afla un întreg $p{~i~}$ reprezentând numărul de elemente din mulţimea $A{~i~}$, urmat de un spaţiu, şi apoi de $p{~i~}$ întregi separaţi prin spaţii, reprezentând elementele din mulţimea $A{~i~}$ într-o ordine oarecare. Fiecare element din mulţimea $A{~i~}$ trebuie să fie un număr natural între $1$ şi $N{~1~}$.
Dacă există mai multe soluţii atunci oricare se consideră corectă.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N{~1~}, N{~2~} ≤ 100 000$
* $1 ≤ M{~1~}, M{~2~} ≤ 200 000$
* $N{~1~} - 1 ≤ M{~1~}$
* $N{~2~} - 1 ≤ M{~2~}$
* Pentru toate testele folosite la corectare reţeaua stradală din Atena verifică cele două proprietăţi enunţate de Parmenide.
h2. Exemplu
table(example). |_. atena.in |_. atena.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 6 6
1 2
2 3
3 4
4 5
5 6
1 6
3 3
7 8
8 9
9 7
| DA
2 1 4
1 2
1 3
|
h3. Explicaţie
...
În exemplul de mai sus, reţeaua stradală a Atenei este formată din $6$ intersecţii legate prin $6$ drumuri, în timp ce reţeaua stradală a Spartei este formată din $3$ intersecţii legate prin $3$ drumuri.
Prima proprietate enunţată de Parmenide este verificată deoarece $6 ≥ 2 * 3$. Cum Atena nu conţine intersecţii incidente cu cel puţin $3$ drumuri, şi a doua proprietate enunţată este verificată.
Putem alege mulţimile disjuncte două câte două şi nevide. Pentru drumul dintre $7$ şi $8$ există un drum între $1$ şi $2$, pentru drumul dintre $8$ şi $9$ există un drum între $2$ şi $3$ iar pentru drumul dintre $9$ şi $7$ există un drum între $4$ şi $3$. Prin urmare, conform definiţiei dată de Pericle reţeaua stradală a Spartei este inclusă în reţeaua stradală a Atenei.
== include(page="template/taskfooter" task_id="atena") ==
