== 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 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
| !problema/clepsidra?graf.png!
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="clepsidra") ==
== include(page="template/taskfooter" task_id="clepsidra") ==
