== include(page="template/taskheader" task_id="clica") ==

Fiind dat un graf **orientat** <tex>G=(V,E)</tex> se consideră următoarea operaţie. Mai întâi se construieşte graful **orientat**  <tex>G^\star=(V,E^\star)</tex>, având aceeaşi mulţime de vârfuri  <tex>V</tex> iar ca arce există un **arc orientat** <tex>(u,v) \in E^\star</tex> dacă şi numai dacă în graful iniţial <tex>G=(V,E)</tex>  există un **drum orientat** de la vârful <tex>u</tex> la vârful <tex>v</tex>. Graful <tex>G^\star=(V,E^\star)</tex> se numeşte închiderea tranzitivă a grafului <tex>G=(V,E)</tex>.

Fiind dat un graf **orientat** <tex>G=(V,E)</tex> se consideră următoarea operaţie. Mai întâi se construieşte graful **orientat** <tex>G^\star=(V,E^\star)</tex>, având aceeaşi mulţime de vârfuri <tex>V</tex> iar ca arce există un **arc orientat** <tex>(u,v) \in E^\star</tex> dacă şi numai dacă în graful iniţial <tex>G=(V,E)</tex> există un **drum orientat** de la vârful <tex>u</tex> la vârful <tex>v</tex>. Graful <tex>G^\star=(V,E^\star)</tex> se numeşte închiderea tranzitivă a grafului <tex>G=(V,E)</tex>.

Se defineşte o **clică** într-un graf orientat ca fiind o submulţime de vârfuri <tex>U</tex> a mulţimii <tex>V</tex>, asfel ca între oricare două vârfuri <tex>u</tex> şi <tex>v</tex> ale lui <tex>U</tex> există un arc orientat fie de la <tex>u</tex> la <tex>v</tex>, fie invers de la <tex>v</tex> la <tex>u</tex> (sau ambele). Dimensiunea unei clici <tex>U</tex> este numărul de vârfuri ale clicii.

h2. Date de intrare

Fişierul de intrare $clica.in$ ...

Fişierul de intrare $clica.in$ conţine mai multe teste. Prima linie a testului conţine două numere întregi <tex>N</tex> şi <tex>M</tex> separate printr-un spaţiu, respectiv numărul de vârfuri şi de arce orientate ale grafului <tex>G</tex>. Următoarea linie conţine <tex>2M</tex> numere întregi separate de spaţiu, fiecare pereche de numere consecutive reprezentând un arc al grafului (vârfurile sunt numere de la 1 la <tex>N</tex>). Este garantat că fiecare arc apare o singură data şi nu există bucle (adică extremităţile fiecărui arc sunt distincte). Fişierul se termină cu numărul **0**.

h2. Date de ieşire

În fişierul de ieşire $clica.out$ ...

Pentru fiecare exemplu de test, în fişierul $clica.out$ se tipăreşte numărul exemplului (începând cu 1) urmat de ':' şi de dimensiunea maximă a unei clici a închiderii tranzitive <tex>G^\star</tex> a grafului dat.

h2. Restricţii

* $... ≤ ... ≤ ...$

* <tex>3 \leq N \leq 10^4</tex>
* <tex>3 \leq M \leq 10^6</tex>

h2. Exemplu
table(example). |_. clica.in |_. clica.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4 4
  1 2 2 3 3 4 4 1
  0
| 1:4

|
h3. Explicaţie

...

Graful din exemplu are 4 vârfuri şi 4 arce: (1, 2), (2, 3), (3, 4) şi (4, 1). Deoarece graful este un ciclu, există un drum orientat între oricare două vârfuri, deci clica maximă conţine toate nodurile grafului.

== include(page="template/taskfooter" task_id="clica") ==