== include(page="template/taskheader" task_id="clepsidra") ==
Poveste şi cerinţă...
Un graf conex cu N noduri şi M muchii poate fi privit ca o clepsidră cu centrul în nodul X, 1 ≤ X ≤ N, dacă putem împărţi toate nodurile, mai puţin nodul X, în două submulţimi nevide astfel încât orice drum de la un nod dintr-o mulţime la un nod din cealaltă mulţime trece prin nodul X. Voi trebuie să determinaţi numărul de moduri distincte în care putem privi graful ca o clepsidră pentru fiecare din cele N noduri alese drept centru, modulo 666013. Două moduri se consideră distincte dacă cele două submulţimi aferente sunt diferite. Ordinea submulţimilor într-un mod este relevantă, dar ordinea nodurilor în cadrul unei mulţimi nu este. Spre exemplu, soluţiile ({1,2,3}, {4,5}) şi ({4,5}, {1,2,3}) sunt distincte, dar soluţiile ({4,5}, {1,2,3}) şi ({4,5}, {1,3,2}) nu sunt distincte.
h2. Date de intrare
Fişierul de intrare $clepsidra.in$ ...
Fişierul de intrare $clepsidra.in$ conţine pe prima linie două numere naturale, N şi M, reprezentând numărul de noduri, respectiv numărul de muchii din graf. Pe următoarele M linii se vor afla câte două numere naturale separate prin câte un spaţiu, reprezentând câte o muchie.
h2. Date de ieşire
În fişierul de ieşire $clepsidra.out$ ...
În fişierul de ieşire $clepsidra.out$ În fişierul de ieşire clepsidra.out se vor afişa N linii. A i-a linie,1 ≤ i ≤ N, va conţine numărul
de moduri în care putem privi graful ca o clepsidră cu centrul în nodul i, modulo 666013.
h2. Restricţii
* $... ≤ ... ≤ ...$
* 2 ≤ N ≤ 200 002
* 1 ≤ M ≤ 250 002
* Pentru 40% din teste avem restricţiile 2 ≤ N ≤ 1002 şi 1 ≤ M ≤ 1502.
* Atentie! Graful este conex.
h2. Exemplu
table(example). |_. clepsidra.in |_. clepsidra.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
table(example). |_. clepsidra.in |_. clepsidra.out |_. Explicaţie |
| 6 7
4 3
1 3
5 4
4 1
3 2
1 5
5 6
| 0
0
2
0
2
0
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="clepsidra") ==
