conex

Numim graf orientat o pereche de mulţimi, notată G = (V, A), unde V este o mulţime de elemente denumite noduri, iar A este o colecţie de perechi ordonate de elemente din V denumite arce. Numim drum într-un graf o succesiune de noduri $x_1, x_2, ..., x_p$ cu proprietatea că oricare ar fi 1 ≤ i < p, există în graf arcul $(x_i, x_{i+1})$. Un graf orientat se numeşte tare conex dacă oricare ar fi x şi y noduri din graf, există în graf cel puţin un drum de la x la y şi cel puţin un drum de la y la x.

Cerinţă

Scrieţi un program care află succesiv arcele unui graf orientat cu N noduri şi verifică după fiecare arc citit dacă graful parţial curent (graful format din cele N vârfuri şi arcele citite până la momentul respectiv) este sau nu tare conex.

Protocol de interacţiune

Programul vostru nu va citi sau scrie din/în niciun fişier și nu va implementa funcția main. În schimb, va avea de implementat funcția

int solve(int N, int M)

ce va interacţiona cu funcția getEdge, unde N reprezintă numărul de noduri din graf, iar M reprezintă numărul de arce din graf. Interacţiunea se desfăşoară conform protocolului descris în continuare.

La momentul iniţial consideraţi că graful parţial curent are N vârfuri şi 0 arce. În continuare putem apela funcția

std::pair<int, int> getEdge()

pentru a obține următorul arc. Odată ce graful parțial obținut este tare conex, solve va trebui să nu mai apeleze funcția getEdge și să returneze 1.

Restricţii şi precizări

• 1 ≤ N ≤ 10 000
• 1 ≤ M ≤ 40 000
• Problema a fost adaptată
• Fișierul "getedge.h" trebuie inclus
• Se garantează ca graful dat este tare conex.
• Arcele nu sunt neapărat distincte.

Exemplu de interacţiune

• Avem N = 4, M = 8
• Graful parţial nu este tare conex, se apelează getEdge() și obținem 1 2
• Graful parţial nu este tare conex, se apelează getEdge() și obținem 3 1
• Graful parţial nu este tare conex, se apelează getEdge() și obținem 2 4
• Graful parţial nu este tare conex, se apelează getEdge() și obținem 2 3
• Graful parţial nu este tare conex, se apelează getEdge() și obținem 4 3
• Graful parţial este tare conex, solve returnează 1