Fişierul intrare/ieşire:	atena.in, atena.out	Sursă	Tabăra ICHB 2012, Ziua 2, Grupa 2
Autor	Dan Constantin Spatarel	Adăugată de	Dan-Constantin Spatarel •spatarel
Timp execuţie pe test	0.2 sec	Limită de memorie	16384 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Atena

Î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ş existau 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₁ intersecţii, legate prin M₁ drumuri bidirecţionale, în timp ce reţeaua stradală a oraşului Sparta avea N₂ intersecţii, legate prin M₂ drumuri bidirecţionale. Intersecţiile din Atena se consideră numerotate cu numere de la 1 la N₁, în timp ce intersecţiile din Sparta se consideră numerotate cu numere de la N₁ + 1 la N₁ + N₂.

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₁, A₂, ..., A_Ni ale mulţimii { 1, 2, ..., N_i } cu proprietatea că pentru orice drum între două intersecţii N₁ + a şi N₁ + 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₂, 1 <= c, d <= N₁.

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₁ ≥ 2 * M₂;
• Oricum am alege o intersecţie a din Atena, şi alte 3 intersecţii distincte b, c şi d legate prin drumuri de a, există un drum între b şi c, sau un drum intre c şi d, sau un drum între b şi d (pot exista chiar două dintre aceste drumuri, sau 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₁, A₂, ..., A_Ni.

Date de intrare

Fişierul de intrare atena.in are următoarea structură:

• pe prima linie se află două numere naturale N₁ şi M₁, reprezentând numărul de intersecţii din Atena, respectiv numărul de drumuri bidirecţionale dintre ele;
• pe liniile 2, ..., M₁ + 1 sunt scrise două numere naturale separate printr-un spaţiu x y (1 ≤ x, y ≤ N₁) cu semnificaţia că între intersecţia x din Atena şi intersecţia y din Atena exista drum;
• pe linia M₁ + 2 se află două numere naturale N₂ şi M₂, reprezentând numărul de intersecţii din Sparta, respectiv numărul de drumuri bidirecţionale dintre ele;
• pe liniile M₁ + 3, ..., M₁ + M₂ + 2 sunt scrise două numere naturale separate printr-un spaţiu x y (N₁ + 1 ≤ x, y ≤ N₁ + N₂) cu semnificaţia că între intersecţia x din Sparta şi intersecţia y din Sparta exista drum.

Date de ieşire

În fişierul de ieşire atena.out se va găsi pe prima linie

Pe prima linie a fişierului atena.out se va găsi 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₂ linii cu următoarea structură:

• pe linia i + 1 (1 ≤ i ≤ N₂) din fişierul atena.out 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₁.

Dacă există mai multe soluţii atunci oricare se consideră corectă.

Restricţii

• 1 ≤ N₁, N₂, M₁, M₂ ≤ 100 000
• N₁ - 1 ≤ M₁
• N₂ - 1 ≤ M₂
• Pentru toate testele folosite la corectare reţeaua stradală din Atena verifică cele două proprietăţi enunţate de Parmenide.

Exemplu

Explicaţie

...

Cum se trimit solutii?