Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | sclifoseala.in, sclifoseala.out | Sursă | Marcel |
Autor | Alexandru Petrescu | Adăugată de | |
Timp execuţie pe test | 1 sec | Limită de memorie | 131072 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Sclifoseala
Marcel a invatat despre forme. Formele pot fi rotunde sau complicate. Lui Marcel ii place ca atunci cand sunt complicate, macar sa fie mici, asa, cat mai irelevante. Spre exemplu un graf poate avea mai multe componente biconexe, fiecare dintre ele fiind reprezentabile fie sub forma unui ciclu simplu rotund elegant, fie este de marime foarte mica.
Astfel, un graf sclifosit este unul neorientat si conex, in care nodul 1 are gradul egal cu 1, si toate componentele sale biconexe fie sunt reprezentabile sub forma unui ciclu simplu fara alte muchii intre nodurile respective, fie contin maxim 8 noduri.
Determinati in cate moduri se poate partitiona un graf sclifosit in doua subgrafuri nevide conexe.
Date de intrare
Fişierul de intrare sclifoseala.in contine pe prima linie numarul T de teste. Structura fiecarui test e urmatoarea: Prima linie contine numarul N de noduri, respectiv M de muchii. Urmatoarele M linii contin perechi de numere naturale a si b reprezentand faptul ca exista o muchie de la a la b.
Date de ieşire
În fişierul de ieşire sclifoseala.out se va afla un singur numar, si anume numarul de partitionari ale grafului dat in doua subgrafuri nevide conexe.
Restricţii
- 1 ≤ T ≤ 3
- 1 ≤ a, b ≤ N, M ≤ 30.000
*h2. Precizare
- Daca sunteti curiosi sa aflati ce este aceea o componenta biconexa, Marcel va recomanda sa invatati: http://www.infoarena.ro/problema/biconex
Exemplu
sclifoseala.in | sclifoseala.out |
---|---|
This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...