Problem p03787 (python)

Fixed submission:
from sys import stdin
from itertools import repeat
from collections import deque
def main():
    n, m = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 2 * m))
    deg = [0] * n
    la = [None] * n
    xt = [0] * (2 * m)
    for i in xrange(m):
        ui = i * 2
        vi = i * 2 + 1
        dat[ui] -= 1
        dat[vi] -= 1
        u = dat[ui]
        v = dat[vi]
        deg[u] += 1
        deg[v] += 1
        xt[vi] = la[u]
        la[u] = vi
        xt[ui] = la[v]
        la[v] = ui
    so = tr = lo = 0
    q = deque()
    done = [0] * n
    pu = q.append
    po = q.popleft
    for i in xrange(n):
        if done[i]:
            continue
        pu(i)
        done[i] = 1
        nu = [i]
        while q:
            x = po()
            y = la[x]
            while y is not None:
                z = dat[y]
                if not done[z]:
                    done[z] = 3 - done[x]
                    pu(z)
                    nu.append(z)
                y = xt[y]
        sd = 0
        pa = 0
        for x in nu:
            sd += deg[x]
            y = la[x]
            while y is not None:
                z = dat[y]
                if done[x] == done[z]:
                    pa = 1
                y = xt[y]
        if sd == 0:
            so += 1
        elif pa:
            lo += 1
        else:
            tr += 1
    print lo * lo + lo * tr * 2 + tr * tr * 2 + so * n * 2 - so * so
main()

Buggy submission (verdict: Runtime Error):
from sys import stdin
from itertools import repeat
from collections import deque
def main():
    n, m = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 2 * m))
    deg = [0] * n
    la = [None] * n
    xt = [0] * (2 * n)
    for i in xrange(m):
        ui = i * 2
        vi = i * 2 + 1
        dat[ui] -= 1
        dat[vi] -= 1
        u = dat[ui]
        v = dat[vi]
        deg[u] += 1
        deg[v] += 1
        xt[vi] = la[u]
        la[u] = vi
        xt[ui] = la[v]
        la[v] = ui
    so = tr = lo = 0
    q = deque()
    done = [0] * n
    pu = q.append
    po = q.popleft
    for i in xrange(n):
        if done[i]:
            continue
        pu(i)
        done[i] = 1
        nu = [i]
        while q:
            x = po()
            y = la[x]
            while y is not None:
                z = dat[y]
                if not done[z]:
                    done[z] = 1
                    pu(z)
                    nu.append(z)
                y = xt[y]
        sd = 0
        for x in nu:
            sd += deg[x]
        if sd == 0:
            so += 1
        elif sd == len(nu) * 2 - 2:
            tr += 1
        else:
            lo += 1
    print lo * lo + lo * tr * 2 + tr * tr * 2 + so * n * 2 - so * so
main()

Buggy submission (verdict: Runtime Error):
from sys import stdin
from itertools import repeat
from collections import deque
def main():
    n, m = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 2 * m))
    deg = [0] * n
    la = [None] * n
    xt = [0] * (2 * n)
    for i in xrange(m):
        ui = i * 2
        vi = i * 2 + 1
        u = dat[ui] - 1
        v = dat[vi] - 1
        deg[u] += 1
        deg[v] += 1
        xt[vi] = la[u]
        la[u] = vi
        xt[ui] = la[v]
        la[v] = ui
    so = tr = lo = 0
    q = []
    done = [0] * n
    pu = q.append
    po = q.pop
    for i in xrange(n):
        if done[i]:
            continue
        pu(i)
        done[i] = 1
        nu = [i]
        while q:
            x = po()
            y = la[x]
            while y is not None:
                z = dat[y] - 1
                if not done[z]:
                    done[z] = 1
                    pu(z)
                    nu.append(z)
                y = xt[y]
        sd = 0
        for x in nu:
            sd += deg[x]
        if sd == 0:
            so += 1
        elif sd == len(nu) * 2 - 2:
            tr += 1
        else:
            lo += 1
    print lo * lo + lo * tr * 2 + tr * tr * 2 + so * n * 2 - so * so
main()