1118 - 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ș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.

Date de ieșire

Fișierul de ieșire clepsidra.out va conține 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.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări

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

Exemplul 1:

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})

Exemplul 2:

clepsidra.in

200200 213
4 3
1 3
5 4
4 1
3 2
1 5
5 6

clepsidra.out

Datele nu corespund restrictiilor impuse

Rezolvare

MOD = 666013

def power(x, y):
    rez = 1
    while y > 0:
        if y % 2 == 1:
            rez = (rez * x) % MOD
        x = (x * x) % MOD
        y = y // 2
    return rez % MOD

def check_constraints(n, m):
    if 2 <= n <= 200002 and 1 <= m <= 250002:
        return True
    else:
        with open("clepsidraOUT.txt", 'w') as out:
            out.write("Datele nu corespund restrictiilor impuse\n")
        return False

def dfs(nc):
    global niv, nmin, nrfii, tati, viz, a, r

    viz[nc] = 1
    niv[nc] = niv[tati[nc]] + 1
    nmin[nc] = niv[nc]
    for nv in a[nc]:
        if viz[nv] == 0:
            tati[nv] = nc
            dfs(nv)
            nmin[nc] = min(nmin[nc], nmin[nv])
            if nc != r and nmin[nv] >= niv[nc]:
                nrfii[nc] += 1

        elif tati[nc] != nv:
            nmin[nc] = min(nmin[nc], niv[nv])

def main():
    global niv, nmin, nrfii, tati, viz, a, r

    with open("clepsidraIN.txt", 'r') as f:
        n, m = map(int, f.readline().split())
        
        if not check_constraints(n, m):
            return
        
        a = [[] for _ in range(n + 1)]
        for _ in range(m):
            x, y = map(int, f.readline().split())
            a[x].append(y)
            a[y].append(x)

    r = 1
    niv = [0] * (n + 1)
    nmin = [0] * (n + 1)
    nrfii = [0] * (n + 1)
    tati = [0] * (n + 1)
    viz = [0] * (n + 1)

    dfs(r)

    with open("clepsidraOUT.txt", 'w') as out:
        if nrfii[r] > 1:
            out.write(str((power(2, nrfii[r]) + MOD - 2) % MOD) + "\n")
        else:
            out.write("0\n")

        for i in range(2, n + 1):
            if nrfii[i] == 0:
                out.write("0\n")
            else:
                out.write(str((power(2, nrfii[i] + 1) + MOD - 2) % MOD) + "\n")

if __name__ == "__main__":
    main()