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 0021 ≤ M ≤ 250 002- Pentru
40%din teste avem restricţiile2 ≤ N ≤ 1002și1 ≤ 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})