clepsidra

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.

Date de intrare

Fișierului 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.

Date de ieșire

Î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.

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.

Exemplu

clepsidra.in

6 7
4 3
1 3
5 4
4 1
3 2
1 5
5 6

clepsidra.out

0
0
2
0
2
0

Explicație

Pentru nodul cu indicele 3, soluţiile sunt: ({2}, {1,4,5,6}) și ({1,4,5,6}, {2})

Pentru nodul cu indicele 5, soluţiile sunt: ({6}, {1,2,3,4}) și ({1,2,3,4},{6})