Hipermetropie

Pe vremea când dacii încă se luptau cu samuraii, într-un colț ascuns al lumii, exista orașul Hipermetropolis, cea mai avansată civilizație din punct de vedere tehnologic de până atunci. Conducătorul acestui oraș, Regele Hip, era un om pasionat de logică și jocuri, așa că își făcea supușii să participe la diferite jocuri care le testau perspicacitatea.

Ne întoarcem în timp într-o zi aleatorie din orașul Hipermetropolis și aflăm că jocul de astăzi este următorul:

Regele alege $N$ supuși (logicieni perfecți) și îi pune într-o pădure (o mulțime de arbori) cu $N$ noduri și $M$ muchii neorientate, fiecare supus fiind într-un nod diferit. Ca toți locuitorii orașului Hipermetropolis, ei sunt hipermetropi (nu pot vedea bine în apropierea lor), așa că un supus nu poate vedea muchiile incidente nodului său, însă poate vedea toate celelalte muchii și toate celelalte noduri.

La începutul jocului, Regele proclamă în fața tuturor supușilor:

„Graful în care vă aflați este o pădure cu cel puțin o muchie.”

După ce supușii primesc această informație, jocul începe. Acesta se desfășoară pe parcursul mai multor runde: la începutul rundei, regele ia pe rând supusul din nodul $1$, apoi pe cel din nodul $2$ ș.a.m.d., și îi întreabă, în secret: „Poți spune cu certitudine că ai cel puțin o muchie incidentă cu nodul tău?”, la care supusul răspunde cu Da sau Nu.

ATENȚIE: regele păstrează secret răspunsul fiecărui participant. Când se termină o rundă, dacă cel puțin un supus a răspuns cu Da, atunci jocul se încheie. În caz contrar, jocul continuă cu o nouă rundă, supușii deducând că toate răspunsurile au fost negative.

Detalii de implementare

Date fiind valorile $N$, $M$ și cele $M$ muchii, se cere determinarea rundei în care se termină jocul, precum și a supușilor care răspund cu Da în acea rundă.

Se cere implementarea următoarei funcții:

std::pair<int, std::vector<int>> solve(int N, std::vector<int> u, std::vector<int> v);

care primește ca parametri:

• $N$, numărul de noduri din graf.
• $u$, vector de mărime $M$
• $v$, vector de mărime $M$

cu semnificația că există muchie neorientată de la $u_i$ la $v_i$, $\forall \ i , 0 \leq i < M$.
Supușii pot fi returnați în orice ordine.
Comisia va apela funcția exact o dată pentru fiecare test.

Restricții și precizări

• $1 \leq M < N \leq 500 \ 000$
• $1 \leq v_i, u_i \leq N$ și $v_i \neq u_i$, $\forall \ 0 \leq i < M$
• Graful descris în datele de intrare este o pădure. Cu alte cuvinte, nu are cicluri.
• Supușii sunt logicieni perfecți și cunosc faptul că toți ceilalți sunt logicieni perfecți.
• Un logician perfect este definit astfel: dacă are suficiente informații să deducă $X$, va deduce $X$.
• Un supus nu va minți niciodată și va răspunde cu Da cât mai repede posibil.
• Se poate demonstra că jocul se termină într-un număr finit de runde.
• Supușii cunosc regulile jocului.
• Toți supușii acceptă mesajul regelui ca fiind adevărat.
• Prima rundă este runda $1$.

Exemplul 1

input

3 2
1 2
1 3

output

1
1

Explicație

Supusul $1$ nu vede nicio muchie în graf și deduce că trebuie să existe cel puțin o muchie incidentă cu el, ceea ce îl face să răspundă cu Da” în prima rundă. Ceilalți doi supuși răspund cu Nu la întrebarea regelui deoarece văd câte o altă muchie.

Exemplul 2

input

4 2
1 2
3 4

output

2
1 2 3 4

Explicație

În prima rundă fiecare supus vede câte o muchie, așa că toată lumea răspunde cu Nu. În a doua rundă, supusul $1$ raționează astfel: „În prima rundă, supusul $3$ a văzut o muchie, dar el este incident cu singura muchie pe care o văd eu: muchia $(3, 4)$, muchie pe care supusul $3$ nu o vede. Asta înseamnă că el trebuie să fi văzut o muchie pe care nu o văd eu, adică o muchie incidentă cu mine.” Ceilalți $3$ supuși raționează analog, și toată lumea răspunde cu Da