Problem p02762 (python)

Fixed submission:
class UnionFind():
    def __init__(self,n):
        # リンク情報　子→親の番号　親(根)→負のサイズ
        self.d=[-1 for i in range(n)]
    
    def find(self,x):
        if(self.d[x]<0):return x
        self.d[x]=self.find(self.d[x])
        return self.d[x]
 
    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if(x==y):return False
        if(self.d[x]>self.d[y]):x,y=y,x
        self.d[x]+=self.d[y]
        self.d[y]=x
        return True
 
    def same(self,x,y):return self.find(x)==self.find(y)
    def size(self,x):return -1*self.d[self.find(x)]
n,m,k=map(int,input().split())
uf=UnionFind(n)
deg=[0 for i in range(n)]
to=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    uf.unite(a,b)
    deg[a]+=1
    deg[b]+=1
for i in range(k):
    a,b=map(int,input().split())
    a-=1
    b-=1
    to[a].append(b)
    to[b].append(a)
for i in range(n):
    ans=uf.size(i)-1-deg[i]
    for j in to[i]:
        if(uf.same(i,j)):ans-=1
    print(ans,end=" ")

Buggy submission (verdict: Runtime Error):
N, M ,K = map(int, input().split())
graph = {}
for m in range(M):
    p,q = map(int, input().split())
    if p-1 in graph.keys():
        graph[p-1].append(q-1)
    else:
        graph[p-1] = [q-1]
    if q-1 in graph.keys():
        graph[q-1].append(p-1)
    else:
        graph[q-1] = [p-1]
bgraph = {}
for k in range(K):
    p,q = map(int, input().split())
    if p-1 in bgraph.keys():
        bgraph[p-1].append(q-1)
    else:
        bgraph[p-1] = [q-1]
    if q-1 in bgraph.keys():
        bgraph[q-1].append(p-1)
    else:
        bgraph[q-1] = [p-1]
output = []
fin_list = [0]*N
for n, i in enumerate(fin_list):
    if i == 1:
        pass
    else:
        seen = [0]*N
        seen[n]=1
        fin_list[n] = 1
        todo =  graph[n].copy()
        while todo != []:
            for j in todo:
                if seen[j] == 1:
#                     print("pass!! seen=={}, j == {}".format(seen, j))
                    todo.remove(j)
                else:
                    todo.extend(graph[j])
                    todo.remove(j)
#                     print("todo=={}___seen=={}___ j=={}".format(todo, seen, j))
                    seen[j] = 1
                    fin_list[j]=1
        smallout = []
        for q, s in enumerate(seen):
            if s == 1:
                smallout.append(q)
        output.append(smallout)
final = []
for n in range(N):
    for w in output:
        if n in w:
            bcount=0
            if n in bgraph.keys():
                for b in bgraph[n]:
                    if b in w:
                        bcount+=1
            final.append(str(len(w)-1-len(graph[n])-bcount))
print(" ".join(final))

Buggy submission (verdict: Runtime Error):
N, M ,K = map(int, input().split())
graph = {}
for m in range(M):
    p,q = map(int, input().split())
    if p-1 in graph.keys():
        graph[p-1].append(q-1)
    else:
        graph[p-1] = [q-1]
    if q-1 in graph.keys():
        graph[q-1].append(p-1)
    else:
        graph[q-1] = [p-1]
bgraph = {}
for k in range(K):
    p,q = map(int, input().split())
    if p-1 in bgraph.keys():
        bgraph[p-1].append(q-1)
    else:
        bgraph[p-1] = [q-1]
    if q-1 in bgraph.keys():
        bgraph[q-1].append(p-1)
    else:
        bgraph[q-1] = [p-1]

output = []
fin_list = [0]*N
for n, i in enumerate(fin_list):
    if i == 1:
        pass
    else:
        seen = [0]*N
        seen[n]=1
        fin_list[n] = 1
        todo =  graph[n].copy()
        while todo != []:
            for j in todo:
                if seen[j] == 1:
#                     print("pass!! seen=={}, j == {}".format(seen, j))
                    todo.remove(j)
                else:
                    todo.extend(graph[j])
                    todo.remove(j)
#                     print("todo=={}___seen=={}___ j=={}".format(todo, seen, j))
                    seen[j] = 1
                    fin_list[j]=1
        smallout = []
        for q, s in enumerate(seen):
            if s == 1:
                smallout.append(q)
        output.append(smallout)

        print("n=={}_____seen{}".format(n, seen))
for n in range(N):
    for w in output:
        if n in w:
            bcount=0
            if n in bgraph.keys():
                for b in bgraph[n]:
                    if b in w:
                        bcount+=1
            print(len(w)-1-len(graph[n])-bcount)