Buggy python submission (verdict: Runtime Error):
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry:
            srx = self.sized(x)
            sry = self.sized(y)
            self.par[rx] = ry
            self.sizes[ry] = srx + sry
        self.root(x)
        self.root(y)

    def same(self, x, y) :
        px = self.root(x)
        py = self.root(y)
        if px == py :
            return True
        else:
            return False

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1)) // 2

def main():
    (n,m) = map(int, input().split())
    ab = []
    for _ in range(m):
        (p,q) = map(int, input().split())
        ab.append((p-1,q-1))
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()


Fixed submission:
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)
        self.rank = array.array('i', [0]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        srx = self.sized(x)
        sry = self.sized(y)
        if rx != ry:
            if self.rank[rx] < self.rank[ry]:
                self.par[rx] = ry
            else:
                self.par[ry] = rx
                if self.rank[rx] == self.rank[ry]:
                    self.rank[rx] = self.rank[rx] + 1
            self.sizes[self.root(rx)] = srx + sry

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1)) // 2

def main():
    (n,m) = map(int, input().split())
    ab = []
    for _ in range(m):
        (p,q) = map(int, input().split())
        ab.append((p-1,q-1))
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        try:
            rx = self.root(x)
            ry = self.root(y)
        except:
            return
        if rx != ry:
            srx = self.sized(x)
            sry = self.sized(y)
            self.par[rx] = ry
            self.sizes[ry] = srx + sry

    def same(self, x, y) :
        try:
            px = self.root(x)
            py = self.root(y)
        except:
            return False
        if px == py :
            return True
        else:
            return False

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1)) // 2

def main():
    (n,m) = map(int, input().split())
    ab = []
    for _ in range(m):
        (p,q) = map(int, input().split())
        ab.append((p-1,q-1))
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()


Fixed submission:
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)
        self.rank = array.array('i', [0]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        srx = self.sized(x)
        sry = self.sized(y)
        if rx != ry:
            if self.rank[rx] < self.rank[ry]:
                self.par[rx] = ry
            else:
                self.par[ry] = rx
                if self.rank[rx] == self.rank[ry]:
                    self.rank[rx] = self.rank[rx] + 1
            self.sizes[self.root(rx)] = srx + sry

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1)) // 2

def main():
    (n,m) = map(int, input().split())
    ab = []
    for _ in range(m):
        (p,q) = map(int, input().split())
        ab.append((p-1,q-1))
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry:
            srx = self.sized(x)
            sry = self.sized(y)
            self.par[rx] = ry
            self.sizes[ry] = srx + sry

    def same(self, x, y) :
        try:
            px = self.root(x)
            py = self.root(y)
        except:
            return False
        if px == py :
            return True
        else:
            return False

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1)) // 2

def main():
    (n,m) = map(int, input().split())
    ab = []
    for _ in range(m):
        (p,q) = map(int, input().split())
        ab.append((p-1,q-1))
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()


Fixed submission:
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)
        self.rank = array.array('i', [0]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        srx = self.sized(x)
        sry = self.sized(y)
        if rx != ry:
            if self.rank[rx] < self.rank[ry]:
                self.par[rx] = ry
            else:
                self.par[ry] = rx
                if self.rank[rx] == self.rank[ry]:
                    self.rank[rx] = self.rank[rx] + 1
            self.sizes[self.root(rx)] = srx + sry

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1)) // 2

def main():
    (n,m) = map(int, input().split())
    ab = []
    for _ in range(m):
        (p,q) = map(int, input().split())
        ab.append((p-1,q-1))
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry:
            srx = self.sized(x)
            sry = self.sized(y)
            self.par[rx] = ry
            self.sizes[ry] = srx + sry

    def same(self, x, y) :
        px = self.root(x)
        py = self.root(y)
        if px == py :
            return True
        else:
            return False

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1)) // 2

def main():
    (n,m) = map(int, input().split())
    ab = []
    for i in range(m):
        (p,q) = map(int, input().split())
        ab.append((p-1,q-1))
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()


Fixed submission:
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)
        self.rank = array.array('i', [0]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        srx = self.sized(x)
        sry = self.sized(y)
        if rx != ry:
            if self.rank[rx] < self.rank[ry]:
                self.par[rx] = ry
            else:
                self.par[ry] = rx
                if self.rank[rx] == self.rank[ry]:
                    self.rank[rx] = self.rank[rx] + 1
            self.sizes[self.root(rx)] = srx + sry

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1)) // 2

def main():
    (n,m) = map(int, input().split())
    ab = []
    for _ in range(m):
        (p,q) = map(int, input().split())
        ab.append((p-1,q-1))
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry:
            srx = self.sized(x)
            sry = self.sized(y)
            self.par[rx] = ry
            self.sizes[ry] = srx + sry

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1)) // 2

def main():
    (n,m) = map(int, input().split())
    ab = []
    for i in range(m):
        (a,b) = map(int, input().split())
        ab.append((a-1,b-1))
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            try:
                score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
                uf.unite(a,b)
                score = score + calsc(uf.sized(a))
            except:
                return
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()


Fixed submission:
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)
        self.rank = array.array('i', [0]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        srx = self.sized(x)
        sry = self.sized(y)
        if rx != ry:
            if self.rank[rx] < self.rank[ry]:
                self.par[rx] = ry
            else:
                self.par[ry] = rx
                if self.rank[rx] == self.rank[ry]:
                    self.rank[rx] = self.rank[rx] + 1
            self.sizes[self.root(rx)] = srx + sry

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1)) // 2

def main():
    (n,m) = map(int, input().split())
    ab = []
    for _ in range(m):
        (p,q) = map(int, input().split())
        ab.append((p-1,q-1))
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry:
            srx = self.sized(x)
            sry = self.sized(y)
            self.par[rx] = ry
            self.sizes[ry] = srx + sry

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1)) // 2

def main():
    (n,m) = map(int, input().split())
    ab = []
    for i in range(m):
        (a,b) = map(int, input().split())
        ab.append((a-1,b-1))
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        try:
            (a,b) = ab.pop()
            #uf.debug()
            res.append(prev)
            score = prev
        except:
            return
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()


Fixed submission:
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)
        self.rank = array.array('i', [0]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        srx = self.sized(x)
        sry = self.sized(y)
        if rx != ry:
            if self.rank[rx] < self.rank[ry]:
                self.par[rx] = ry
            else:
                self.par[ry] = rx
                if self.rank[rx] == self.rank[ry]:
                    self.rank[rx] = self.rank[rx] + 1
            self.sizes[self.root(rx)] = srx + sry

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1)) // 2

def main():
    (n,m) = map(int, input().split())
    ab = []
    for _ in range(m):
        (p,q) = map(int, input().split())
        ab.append((p-1,q-1))
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry:
            srx = self.sized(x)
            sry = self.sized(y)
            self.par[rx] = ry
            self.sizes[ry] = srx + sry

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1)) // 2

def main():
    (n,m) = map(int, input().split())
    ab = []
    for i in range(m):
        (a,b) = map(int, input().split())
        ab.append((a-1,b-1))
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            try :
                uf.unite(a,b)
            except:
                return
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()


Fixed submission:
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)
        self.rank = array.array('i', [0]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        srx = self.sized(x)
        sry = self.sized(y)
        if rx != ry:
            if self.rank[rx] < self.rank[ry]:
                self.par[rx] = ry
            else:
                self.par[ry] = rx
                if self.rank[rx] == self.rank[ry]:
                    self.rank[rx] = self.rank[rx] + 1
            self.sizes[self.root(rx)] = srx + sry

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1)) // 2

def main():
    (n,m) = map(int, input().split())
    ab = []
    for _ in range(m):
        (p,q) = map(int, input().split())
        ab.append((p-1,q-1))
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry:
            srx = self.sized(x)
            sry = self.sized(y)
            self.par[rx] = ry
            self.sizes[ry] = srx + sry

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1)) // 2

def main():
    (n,m) = map(int, input().split())
    ab = []
    for i in range(m):
        (a,b) = map(int, input().split())
        ab.append((a-1,b-1))
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()


Fixed submission:
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)
        self.rank = array.array('i', [0]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        srx = self.sized(x)
        sry = self.sized(y)
        if rx != ry:
            if self.rank[rx] < self.rank[ry]:
                self.par[rx] = ry
            else:
                self.par[ry] = rx
                if self.rank[rx] == self.rank[ry]:
                    self.rank[rx] = self.rank[rx] + 1
            self.sizes[self.root(rx)] = srx + sry

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1)) // 2

def main():
    (n,m) = map(int, input().split())
    ab = []
    for _ in range(m):
        (p,q) = map(int, input().split())
        ab.append((p-1,q-1))
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if(rx == ry):
            return
        self.par[rx] = ry
        rrx = self.root(x)
        self.sizes[rrx] = self.sizes[rx] + self.sizes[ry]

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1L)) // 2L

def main():
    (n,m) = map(int, input().split())
    ab = []
    for i in range(m):
        (a,b) = map(int, input().split())
        ab.append((a-1,b-1))
    uf = UnionFind(n)
    res = []
    prev = 0L
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()


Fixed submission:
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)
        self.rank = array.array('i', [0]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        srx = self.sized(x)
        sry = self.sized(y)
        if rx != ry:
            if self.rank[rx] < self.rank[ry]:
                self.par[rx] = ry
            else:
                self.par[ry] = rx
                if self.rank[rx] == self.rank[ry]:
                    self.rank[rx] = self.rank[rx] + 1
            self.sizes[self.root(rx)] = srx + sry

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1)) // 2

def main():
    (n,m) = map(int, input().split())
    ab = []
    for _ in range(m):
        (p,q) = map(int, input().split())
        ab.append((p-1,q-1))
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if(rx == ry):
            return
        self.par[rx] = ry
        rrx = self.root(x)
        self.sizes[rrx] = self.sizes[rx] + self.sizes[ry]

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1)) // 2

def main():
    (n,m) = map(int, input().split())
    ab = []
    for i in range(m):
        (a,b) = map(int, input().split())
        ab.append((a-1,b-1))
    #ab = ab[::-1]
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()


Fixed submission:
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)
        self.rank = array.array('i', [0]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        srx = self.sized(x)
        sry = self.sized(y)
        if rx != ry:
            if self.rank[rx] < self.rank[ry]:
                self.par[rx] = ry
            else:
                self.par[ry] = rx
                if self.rank[rx] == self.rank[ry]:
                    self.rank[rx] = self.rank[rx] + 1
            self.sizes[self.root(rx)] = srx + sry

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1)) // 2

def main():
    (n,m) = map(int, input().split())
    ab = []
    for _ in range(m):
        (p,q) = map(int, input().split())
        ab.append((p-1,q-1))
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if(rx == ry):
            return
        self.par[rx] = ry
        rrx = self.root(x)
        self.sizes[rrx] = self.sizes[rx] + self.sizes[ry]

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def main():
    (n,m) = map(int, input().split())
    ab = []
    for i in range(m):
        (a,b) = map(int, input().split())
        ab.append((a-1,b-1))
    #ab = ab[::-1]
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

def calsc(x):
    return (x * (x-1)) // 2

if __name__ == '__main__':
    main()


Fixed submission:
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)
        self.rank = array.array('i', [0]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        srx = self.sized(x)
        sry = self.sized(y)
        if rx != ry:
            if self.rank[rx] < self.rank[ry]:
                self.par[rx] = ry
            else:
                self.par[ry] = rx
                if self.rank[rx] == self.rank[ry]:
                    self.rank[rx] = self.rank[rx] + 1
            self.sizes[self.root(rx)] = srx + sry

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1)) // 2

def main():
    (n,m) = map(int, input().split())
    ab = []
    for _ in range(m):
        (p,q) = map(int, input().split())
        ab.append((p-1,q-1))
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if(rx == ry):
            return
        self.par[rx] = ry
        rrx = self.root(x)
        self.sizes[rrx] = self.sizes[rx] + self.sizes[ry]

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def main():
    (n,m) = map(int, input().split())
    ab = []
    for i in range(m):
        (a,b) = map(int, input().split())
        ab.append((a-1,b-1))
    #ab = ab[::-1]
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        if uf.same(a,b):
            score = prev
        else:
            score = prev - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

def calsc(x):
    return (x * (x-1)) // 2

if __name__ == '__main__':
    main()


Fixed submission:
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)
        self.rank = array.array('i', [0]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        srx = self.sized(x)
        sry = self.sized(y)
        if rx != ry:
            if self.rank[rx] < self.rank[ry]:
                self.par[rx] = ry
            else:
                self.par[ry] = rx
                if self.rank[rx] == self.rank[ry]:
                    self.rank[rx] = self.rank[rx] + 1
            self.sizes[self.root(rx)] = srx + sry

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1)) // 2

def main():
    (n,m) = map(int, input().split())
    ab = []
    for _ in range(m):
        (p,q) = map(int, input().split())
        ab.append((p-1,q-1))
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if(rx == ry):
            return
        self.par[rx] = ry
        rrx = self.root(x)
        self.sizes[rrx] = self.sizes[rx] + self.sizes[ry]

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def size(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def main():
    (n,m) = map(int, input().split())
    ab = []
    for i in range(m):
        (a,b) = map(int, input().split())
        ab.append((a-1,b-1))
    #ab = ab[::-1]
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        if uf.same(a,b):
            score = prev
        else:
            score = prev - calsc(uf.size(a)) - calsc(uf.size(b))
            uf.unite(a,b)
            score = score + calsc(uf.size(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

def calsc(x):
    return (x * (x-1)) // 2

if __name__ == '__main__':
    main()


Fixed submission:
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)
        self.rank = array.array('i', [0]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        srx = self.sized(x)
        sry = self.sized(y)
        if rx != ry:
            if self.rank[rx] < self.rank[ry]:
                self.par[rx] = ry
            else:
                self.par[ry] = rx
                if self.rank[rx] == self.rank[ry]:
                    self.rank[rx] = self.rank[rx] + 1
            self.sizes[self.root(rx)] = srx + sry

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1)) // 2

def main():
    (n,m) = map(int, input().split())
    ab = []
    for _ in range(m):
        (p,q) = map(int, input().split())
        ab.append((p-1,q-1))
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if(rx == ry):
            return
        self.par[rx] = ry
        rrx = self.root(x)
        self.sizes[rrx] = self.sizes[rx] + self.sizes[ry]

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def size(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def main():
    (n,m) = map(int, input().split())
    ab = []
    for i in range(m):
        (a,b) = map(int, input().split())
        ab.append((a-1,b-1))
    ab = ab[::-1]
    uf = UnionFind(n)
    res = []
    prev = 0
    for (a,b) in ab:
        #uf.debug()
        res.append(prev)
        if uf.same(a,b):
            score = prev
        else:
            score = prev - calsc(uf.size(a)) - calsc(uf.size(b))
            uf.unite(a,b)
            score = score + calsc(uf.size(a))
        prev = score
    time.sleep(30)
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

def calsc(x):
    return (x * (x-1)) // 2

if __name__ == '__main__':
    main()


Fixed submission:
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)
        self.rank = array.array('i', [0]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        srx = self.sized(x)
        sry = self.sized(y)
        if rx != ry:
            if self.rank[rx] < self.rank[ry]:
                self.par[rx] = ry
            else:
                self.par[ry] = rx
                if self.rank[rx] == self.rank[ry]:
                    self.rank[rx] = self.rank[rx] + 1
            self.sizes[self.root(rx)] = srx + sry

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1)) // 2

def main():
    (n,m) = map(int, input().split())
    ab = []
    for _ in range(m):
        (p,q) = map(int, input().split())
        ab.append((p-1,q-1))
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if(rx == ry):
            return
        self.par[rx] = ry
        rrx = self.root(x)
        self.sizes[rrx] = self.sizes[rx] + self.sizes[ry]

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def size(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def main():
    (n,m) = map(int, input().split())
    ab = []
    for i in range(m):
        (a,b) = map(int, input().split())
        ab.append((a-1,b-1))
    ab = ab[::-1]
    uf = UnionFind(n)
    res = []
    prev = 0
    time.sleep(30)
    for (a,b) in ab:
        #uf.debug()
        res.append(prev)
        if uf.same(a,b):
            score = prev
        else:
            score = prev - calsc(uf.size(a)) - calsc(uf.size(b))
            uf.unite(a,b)
            score = score + calsc(uf.size(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

def calsc(x):
    return (x * (x-1)) // 2

if __name__ == '__main__':
    main()


Fixed submission:
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)
        self.rank = array.array('i', [0]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        srx = self.sized(x)
        sry = self.sized(y)
        if rx != ry:
            if self.rank[rx] < self.rank[ry]:
                self.par[rx] = ry
            else:
                self.par[ry] = rx
                if self.rank[rx] == self.rank[ry]:
                    self.rank[rx] = self.rank[rx] + 1
            self.sizes[self.root(rx)] = srx + sry

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1)) // 2

def main():
    (n,m) = map(int, input().split())
    ab = []
    for _ in range(m):
        (p,q) = map(int, input().split())
        ab.append((p-1,q-1))
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import array

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if(rx == ry):
            return
        self.par[rx] = ry
        rrx = self.root(x)
        self.sizes[rrx] = self.sizes[rx] + self.sizes[ry]

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def size(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def main():
    (n,m) = map(int, input().split())
    ab = []
    for i in range(m):
        (a,b) = map(int, input().split())
        ab.append((a-1,b-1))
    ab = ab[::-1]
    uf = UnionFind(n)
    res = []
    prev = 0
    for (a,b) in ab:
        #uf.debug()
        res.append(prev)
        if uf.same(a,b):
            score = prev
        else:
            score = prev - calsc(uf.size(a)) - calsc(uf.size(b))
            uf.unite(a,b)
            score = score + calsc(uf.size(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

def calsc(x):
    return (x * (x-1)) // 2


if __name__ == '__main__':
    main()


Fixed submission:
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)
        self.rank = array.array('i', [0]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        srx = self.sized(x)
        sry = self.sized(y)
        if rx != ry:
            if self.rank[rx] < self.rank[ry]:
                self.par[rx] = ry
            else:
                self.par[ry] = rx
                if self.rank[rx] == self.rank[ry]:
                    self.rank[rx] = self.rank[rx] + 1
            self.sizes[self.root(rx)] = srx + sry

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1)) // 2

def main():
    (n,m) = map(int, input().split())
    ab = []
    for _ in range(m):
        (p,q) = map(int, input().split())
        ab.append((p-1,q-1))
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import array

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if(rx == ry):
            return
        self.par[rx] = ry
        rrx = self.root(x)
        self.sizes[rrx] = self.sizes[rx] + self.sizes[ry]

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def size(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def main():
    (n,m) = map(int, input().split())
    ab = []
    for i in range(m):
        (a,b) = map(int, input().split())
        ab.append((a-1,b-1))
    ab = ab[::-1]
    uf = UnionFind(n)
    res = []
    prev = 0
    for (a,b) in ab:
        #uf.debug()
        res.append(prev)
        if uf.same(a,b):
            score = prev
        else:
            score = prev - calsc(uf.size(a)) - calsc(uf.size(b))
            uf.unite(a,b)
            score = score + calsc(uf.size(uf.root(a)))
        prev = score
    for i in range(m):
        res[i] = ((n*(n-1)) // 2) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

def calsc(x):
    return (x * (x-1)) // 2

def calcScore(uf, n, prev):
    nroots = array.array('i', [0] * n)
    for i in range(n):
        root = uf.root(i)
        nroots[root] = nroots[root] + 1
    res = 0
    for r in nroots:
        res = res + (r * (r-1)) // 2
    return res

if __name__ == '__main__':
    main()


Fixed submission:
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)
        self.rank = array.array('i', [0]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        srx = self.sized(x)
        sry = self.sized(y)
        if rx != ry:
            if self.rank[rx] < self.rank[ry]:
                self.par[rx] = ry
            else:
                self.par[ry] = rx
                if self.rank[rx] == self.rank[ry]:
                    self.rank[rx] = self.rank[rx] + 1
            self.sizes[self.root(rx)] = srx + sry

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1)) // 2

def main():
    (n,m) = map(int, input().split())
    ab = []
    for _ in range(m):
        (p,q) = map(int, input().split())
        ab.append((p-1,q-1))
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import array

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r


    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if(rx == ry):
            return
        self.par[rx] = ry
        self.root(x)

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def debug(self):
        print(self.par)



def main():
    (n,m) = map(int, input().split())
    ab = []
    for i in range(m):
        (a,b) = map(int, input().split())
        ab.append((a-1,b-1))
    ab = ab[::-1]
    uf = UnionFind(n)
    res = []
    for (a,b) in ab:
        res.append(calcScore(uf, n))
        uf.unite(a,b)
    for i in range(m):
        res[i] = ((n*(n-1)) // 2) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

def calcScore(uf, n):
    nroots = array.array('i', [0] * n)
    for i in range(n):
        root = uf.root(i)
        nroots[root] = nroots[root] + 1
    res = 0
    for r in nroots:
        res = res + (r * (r-1)) // 2
    return res

if __name__ == '__main__':
    main()


Fixed submission:
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)
        self.rank = array.array('i', [0]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        srx = self.sized(x)
        sry = self.sized(y)
        if rx != ry:
            if self.rank[rx] < self.rank[ry]:
                self.par[rx] = ry
            else:
                self.par[ry] = rx
                if self.rank[rx] == self.rank[ry]:
                    self.rank[rx] = self.rank[rx] + 1
            self.sizes[self.root(rx)] = srx + sry

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1)) // 2

def main():
    (n,m) = map(int, input().split())
    ab = []
    for _ in range(m):
        (p,q) = map(int, input().split())
        ab.append((p-1,q-1))
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import array

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r


    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if(rx == ry):
            return
        self.par[rx] = ry
        self.root(x)

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def debug(self):
        print(self.par)

if __name__ == '__main__':
    main()

def main():
    (n,m) = map(int, input().split())
    ab = []
    for i in range(m):
        (a,b) = map(int, input().split())
        ab.append((a-1,b-1))
    ab = ab[::-1]
    uf = UnionFind(n)
    res = []
    for (a,b) in ab:
        res.append(calcScore(uf, n))
        uf.unite(a,b)
    for i in range(m):
        res[i] = ((n*(n-1)) // 2) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

def calcScore(uf, n):
    nroots = array.array('i', [0] * n)
    for i in range(n):
        root = uf.root(i)
        nroots[root] = nroots[root] + 1
    res = 0
    for r in nroots:
        res = res + (r * (r-1)) // 2
    return res


Fixed submission:
import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)
        self.rank = array.array('i', [0]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        srx = self.sized(x)
        sry = self.sized(y)
        if rx != ry:
            if self.rank[rx] < self.rank[ry]:
                self.par[rx] = ry
            else:
                self.par[ry] = rx
                if self.rank[rx] == self.rank[ry]:
                    self.rank[rx] = self.rank[rx] + 1
            self.sizes[self.root(rx)] = srx + sry

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1)) // 2

def main():
    (n,m) = map(int, input().split())
    ab = []
    for _ in range(m):
        (p,q) = map(int, input().split())
        ab.append((p-1,q-1))
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()