Problem:


Score : 400 points

Problem Statement

An SNS has N users - User 1, User 2, \cdots, User N.

Between these N users, there are some relationships - M friendships and K blockships.

For each i = 1, 2, \cdots, M, there is a bidirectional friendship between User A_i and User B_i.

For each i = 1, 2, \cdots, K, there is a bidirectional blockship between User C_i and User D_i.

We define User a to be a friend candidate for User b when all of the following four conditions are satisfied:

a \neq b.

There is not a friendship between User a and User b.

There is not a blockship between User a and User b.

There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a, c_L = b, and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1.

For each user i = 1, 2, ... N, how many friend candidates does it have?

Constraints

All values in input are integers.

2 ≤ N ≤ 10^5

0 \leq M \leq 10^5

0 \leq K \leq 10^5

1 \leq A_i, B_i \leq N

A_i \neq B_i

1 \leq C_i, D_i \leq N

C_i \neq D_i

(A_i, B_i) \neq (A_j, B_j) (i \neq j)

(A_i, B_i) \neq (B_j, A_j)

(C_i, D_i) \neq (C_j, D_j) (i \neq j)

(C_i, D_i) \neq (D_j, C_j)

(A_i, B_i) \neq (C_j, D_j)

(A_i, B_i) \neq (D_j, C_j)

Input

Input is given from Standard Input in the following format:

N M K
A_1 B_1
\vdots
A_M B_M
C_1 D_1
\vdots
C_K D_K

Output

Print the answers in order, with space in between.

Sample Input 1

4 4 1
2 1
1 3
3 2
3 4
4 1

Sample Output 1

0 1 0 1

There is a friendship between User 2 and 3, and between 3 and 4. Also, there is no friendship or blockship between User 2 and 4. Thus, User 4 is a friend candidate for User 2.

However, neither User 1 or 3 is a friend candidate for User 2, so User 2 has one friend candidate.

Sample Input 2

5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5

Sample Output 2

0 0 0 0 0

Everyone is a friend of everyone else and has no friend candidate.

Sample Input 3

10 9 3
10 1
6 7
8 2
2 5
8 4
7 3
10 9
6 4
5 8
2 6
7 5
3 1

Sample Output 3

1 3 5 4 3 3 3 3 1 0



Sample input:
4 4 1
2 1
1 3
3 2
3 4
4 1


Sample output:
0 1 0 1

Submission status: Time Limit Exceeded

Solution code:
import queue
def main():
    n,m,k=map(int,input().split())
    root={}
    ng={}
    friend=[[0 for i in range(n)]for i in range(n)]
    for i in range(n):
        root[i]=[]
        ng[i]=[0]*n
        ng[i][i]=1
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1].append(b-1)
        root[b-1].append(a-1)
        friend[a-1][b-1]=1
        friend[b-1][a-1]=1
    for i in range(k):
        a,b=map(int,input().split())
        ng[a-1][b-1]=1
        ng[b-1][a-1]=1
    
    Vstd=[]
    checkVst=[0]*n
    num=[0]*n
    ToVst=queue.Queue()
    for i in range(n):
        Vstd=[]
        if checkVst[i]==1:
            continue
        now=i
        Vstd.append(now)
        checkVst[now]=1
        for kouho in root[now]:
            if checkVst[kouho]!=1:
                ToVst.put(kouho)
                checkVst[kouho]=1
        while ToVst.empty()==False:
            now=ToVst.get()
            Vstd.append(now)
            checkVst[now]=1
            for kouho in root[now]:
                if checkVst[kouho]==1:
                    continue
                ToVst.put(kouho)
                checkVst[kouho]=1

        l=len(Vstd)
        for x in Vstd:
            num[x]=l
            
            for y in Vstd:
                if ng[x][y]==1 or friend[x][y]==1:
                    num[x]-=1
    print(*num)
    #print(" ".join(map(str,num)))
   

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
def main():
    n,m,k=map(int,input().split())
    root={}
    ng={}
    friend=[[0 for i in range(n)]for i in range(n)]
    for i in range(n):
        root[i]=[]
        ng[i]=[0]*n
        ng[i][i]=1
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1].append(b-1)
        root[b-1].append(a-1)
        friend[a-1][b-1]=1
        friend[b-1][a-1]=1
    for i in range(k):
        a,b=map(int,input().split())
        ng[a-1][b-1]=1
        ng[b-1][a-1]=1
    
    Vstd=[]
    checkVst=[0]*n
    num=[0]*n
    ToVst=queue.Queue()
    for i in range(n):
        Vstd=[]
        if checkVst[i]==1:
            continue
        now=i
        Vstd.append(now)
        checkVst[now]=1
        for kouho in root[now]:
            if checkVst[kouho]!=1:
                ToVst.put(kouho)
                checkVst[kouho]=1
        while ToVst.empty()==False:
            now=ToVst.get()
            Vstd.append(now)
            checkVst[now]=1
            for kouho in root[now]:
                if checkVst[kouho]==1:
                    continue
                ToVst.put(kouho)
                checkVst[kouho]=1

        l=len(Vstd)
        for x in Vstd:
            num[x]=l
            for y in Vstd:
                if ng[x][y]==1 or friend[x][y]==1:
                    num[x]-=1
    print(*num)
    #print(" ".join(map(str,num)))
   

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
def main():
    n,m,k=map(int,input().split())
    root={}
    ng={}
    friend={}
    for i in range(n):
        root[i]=[]
        ng[i]=[0]*n
        ng[i][i]=1
        friend[i]=[0]*n
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1].append(b-1)
        root[b-1].append(a-1)
        friend[a-1][b-1]=1
        friend[b-1][a-1]=1
    for i in range(k):
        a,b=map(int,input().split())
        ng[a-1][b-1]=1
        ng[b-1][a-1]=1
    
    Vstd=[]
    checkVst=[0]*n
    num=[0]*n
    ToVst=queue.Queue()
    for i in range(n):
        Vstd=[]
        if checkVst[i]==1:
            continue
        now=i
        Vstd.append(now)
        checkVst[now]=1
        for kouho in root[now]:
            if checkVst[kouho]!=1:
                ToVst.put(kouho)
                checkVst[kouho]=1
        while ToVst.empty()==False:
            now=ToVst.get()
            Vstd.append(now)
            checkVst[now]=1
            for kouho in root[now]:
                if checkVst[kouho]==1:
                    continue
                ToVst.put(kouho)
                checkVst[kouho]=1

        l=len(Vstd)
        for x in Vstd:
            num[x]=l
            for y in Vstd:
                if ng[x][y]==1 or friend[x][y]==1:
                    num[x]-=1
    print(*num)
    #print(" ".join(map(str,num)))
   

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
def main():
    n,m,k=map(int,input().split())
    root={}
    ng={}
    for i in range(n):
        root[i]=[]
        ng[i]=[0]*n
        ng[i][i]=1
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1].append(b-1)
        root[b-1].append(a-1)
    for i in range(k):
        a,b=map(int,input().split())
        ng[a-1][b-1]=1
        ng[b-1][a-1]=1
    
    Vstd=[]
    checkVst=[0]*n
    num=[0]*n
    ToVst=queue.Queue()
    for i in range(n):
        Vstd=[]
        if checkVst[i]==1:
            continue
        now=i
        Vstd.append(now)
        checkVst[now]=1
        for kouho in root[now]:
            if checkVst[kouho]!=1:
                ToVst.put(kouho)
                checkVst[kouho]=1
        while ToVst.empty()==False:
            now=ToVst.get()
            Vstd.append(now)
            checkVst[now]=1
            for kouho in root[now]:
                if checkVst[kouho]==1:
                    continue
                ToVst.put(kouho)
                checkVst[kouho]=1

        l=len(Vstd)
        for x in Vstd:
            num[x]=l
            for y in Vstd:
                if ng[x][y]==1 or y in root[x]:
                    num[x]-=1
    print(*num)
    #print(" ".join(map(str,num)))
   

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
def main():
    n,m,k=map(int,input().split())
    root={}
    ng={}
    for i in range(n):
        root[i]=[]
        ng[i]=[i]
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1].append(b-1)
        root[b-1].append(a-1)
    for i in range(k):
        a,b=map(int,input().split())
        ng[a-1].append(b-1)
        ng[b-1].append(a-1)
    
    Vstd=[]
    checkVst=[0]*n
    num=[0]*n
    ToVst=queue.Queue()
    for i in range(n):
        Vstd=[]
        if checkVst[i]==1:
            continue
        now=i
        Vstd.append(now)
        checkVst[now]=1
        for kouho in root[now]:
            if checkVst[kouho]!=1:
                ToVst.put(kouho)
                checkVst[kouho]=1
        while ToVst.empty()==False:
            now=ToVst.get()
            Vstd.append(now)
            checkVst[now]=1
            for kouho in root[now]:
                if checkVst[kouho]==1:
                    continue
                ToVst.put(kouho)
                checkVst[kouho]=1

        l=len(Vstd)
        for x in Vstd:
            num[x]=l
            for y in Vstd:
                if y in ng[x] or y in root[x]:
                    num[x]-=1
    print(*num)
    #print(" ".join(map(str,num)))
   

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
def main():
    n,m,k=map(int,input().split())
    root={}
    ng={}
    for i in range(n):
        root[i]=[]
        ng[i]=[i]
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1].append(b-1)
        root[b-1].append(a-1)
    for i in range(k):
        a,b=map(int,input().split())
        ng[a-1].append(b-1)
        ng[b-1].append(a-1)
    
    Vstd=[]
    checkVst=[0]*n
    num=[0]*n
    ToVst=queue.Queue()
    for i in range(n):
        Vstd=[]
        if checkVst[i]==1:
            continue
        now=i
        Vstd.append(now)
        checkVst[now]=1
        for kouho in root[now]:
            if checkVst[kouho]!=1:
                ToVst.put(kouho)
                checkVst[kouho]=1
        while ToVst.empty()==False:
            now=ToVst.get()
            Vstd.append(now)
            checkVst[now]=1
            for kouho in root[now]:
                if checkVst[kouho]==1:
                    continue
                ToVst.put(kouho)
                checkVst[kouho]=1
       #         print("a")

      #  print(Vstd)
        for x in Vstd:
            num[x]=len(Vstd)
            for y in Vstd:
                if y in ng[x] or y in root[x]:
                    num[x]-=1
    print(*num)
    #print(" ".join(map(str,num)))
   

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
def main():
    n,m,k=map(int,input().split())
    root={}
    ng={}
    for i in range(n):
        root[i]=[]
        ng[i]=[i]
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1].append(b-1)
        root[b-1].append(a-1)
    for i in range(k):
        a,b=map(int,input().split())
        ng[a-1].append(b-1)
        ng[b-1].append(a-1)
    
    Vstd=[]
    checkVst=[0]*n
    num=[0]*n
    ToVst=queue.Queue()
    for i in range(n):
        Vstd=[]
        if checkVst[i]==1:
            continue
        now=i
        Vstd.append(now)
        checkVst[now]=1
        for kouho in root[now]:
            if checkVst[kouho]!=1:
                ToVst.put(kouho)
                checkVst[kouho]=1
        while ToVst.empty()==False:
            now=ToVst.get()
            Vstd.append(now)
            checkVst[now]=1
            for kouho in root[now]:
                if checkVst[kouho]==1:
                    continue
                ToVst.put(kouho)
                checkVst[kouho]=1
       #         print("a")

      #  print(Vstd)
        for x in Vstd:
            num[x]=len(Vstd)
            for y in Vstd:
                if y in ng[x] or y in root[x]:
                    num[x]-=1
    print(" ".join(map(str,num)))
    




        
        




        


if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n # 親(uf.find()で経路圧縮して根)の番号。根の場合は-(そのグループの要素数)
    def find(self,x):
        #グループの根を返す
        if self.parents[x]<0:return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        #要素x,yのグループを併合
        x,y=self.find(x),self.find(y)
        if x==y:return
        if self.parents[x]>self.parents[y]:#要素数の大きい方をxに
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x #要素数が大きい方に併合
    def size(self,x):
        #xが属するグループの要素数
        return -self.parents[self.find(x)]
    def same(self,x,y):
        #xとyが同じグループ？
        return self.find(x)==self.find(y)
    def members(self,x):
        #xと同じグループに属する要素のリスト
        root=self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]
    def roots(self):
        #全ての根の要素のリスト
        return [i for i, x in enumerate(self.parents) if x<0]
    def group_count(self):
        #グループの数
        return len(self.roots())
    def all_group_members(self):
        #各ルート要素のグループに含まれる要素のリストの辞書
        return {r: self.members(r) for r in self.roots()}
    def all_group_members_list(self):
        #各ルート要素のグループに含まれる要素のリストのリスト
        #[[0, 2], [1, 3, 4, 5]]
        return list(self.all_group_members().values())
    def __str__(self):
        #各ルート要素のグループに含まれる要素のリストをprint()
        return '\n'.join('{}: {}'.format(r,self.members(r)) for r in self.roots())

def main():
    n,m,k=map(int,input().split())
    AB=[tuple(map(int,input().split())) for i in range(m)]
    CD=[tuple(map(int,input().split())) for i in range(k)]
    un=UnionFind(n)
    friend=[[] for _ in range(n)]
    for a,b in AB:
        un.unite(a-1,b-1)
        friend[a-1].append(b-1)
        friend[b-1].append(a-1)
    block=[[] for _ in range(n)]
    for c,d in CD:
        block[c-1].append(d-1)
        block[d-1].append(c-1)
    for i in range(n):
        print(len([x for x in un.members(i) if x!=i and (not x in block[i]) and (not x in friend[i])]))
 
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n # 親(uf.find()で経路圧縮して根)の番号。根の場合は-(そのグループの要素数)
    def find(self,x):
        #グループの根を返す
        if self.parents[x]<0:return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        #要素x,yのグループを併合
        x,y=self.find(x),self.find(y)
        if x==y:return
        if self.parents[x]>self.parents[y]:#要素数の大きい方をxに
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x #要素数が大きい方に併合
    def size(self,x):
        #xが属するグループの要素数
        return -self.parents[self.find(x)]
    def same(self,x,y):
        #xとyが同じグループ？
        return self.find(x)==self.find(y)
    def members(self,x):
        #xと同じグループに属する要素のリスト
        root=self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]
    def roots(self):
        #全ての根の要素のリスト
        return [i for i, x in enumerate(self.parents) if x<0]
    def group_count(self):
        #グループの数
        return len(self.roots())
    def all_group_members(self):
        #各ルート要素のグループに含まれる要素のリストの辞書
        return {r: self.members(r) for r in self.roots()}
    def all_group_members_list(self):
        #各ルート要素のグループに含まれる要素のリストのリスト
        #[[0, 2], [1, 3, 4, 5]]
        return list(self.all_group_members().values())
    def __str__(self):
        #各ルート要素のグループに含まれる要素のリストをprint()
        return '\n'.join('{}: {}'.format(r,self.members(r)) for r in self.roots())

class UnionFindLabel(UnionFind):
    def __init__(self, labels):
        assert len(labels)==len(set(labels))
        self.n=len(labels)
        self.parents=[-1]*self.n
        self.d={x: i for i,x in enumerate(labels)}
        self.d_inv={i: x for i,x in enumerate(labels)}
    def find_label(self,x):
        return self.d_inv[super().find(self.d[x])]
    def unite(self,x,y):
        super().unite(self.d[x],self.d[y])
    def size(self,x):
        return super().size(self.d[x])
    def same(self,x,y):
        return super().same(self.d[x],self.d[y])
    def members(self,x):
        root=self.find(self.d[x])
        return [self.d_inv[i] for i in range(self.n) if self.find(i)==root]
    def roots(self):
        return [self.d_inv[i] for i,x in enumerate(self.parents) if x<0]

def main():
    n,m,k=map(int,input().split())
    AB=[tuple(map(int,input().split())) for i in range(m)]
    CD=[tuple(map(int,input().split())) for i in range(k)]
    un=UnionFindLabel(range(1,n+1))
    friend=[[] for _ in range(n)]
    for a,b in AB:
        un.unite(a,b)
        friend[a-1].append(b)
        friend[b-1].append(a)
    block=[[] for _ in range(n)]
    for c,d in CD:
        block[c-1].append(d)
        block[d-1].append(c)
    for i in range(1,n+1):
        print(len([x for x in un.members(i) if x!=i and (not x in block[i-1]) and  (not x in friend[i-1])]))
 
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
import numpy
def main():
    n,m,k=map(int,input().split())
    root=numpy.array([[0]*n for i in range(n)])
    for i in range(n):
        root[i][i]=2
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1][b-1]=1
        root[b-1][a-1]=1
    for i in range(k):
        a,b=map(int,input().split())
        root[a-1][b-1]=-100
        root[b-1][a-1]=-100
    toVis=queue.Queue()
    Visted=[]
    checkOK=numpy.zeros(n)#その点に関しての友達候補つくり済みかどうか
    OK={}#友達候補リスト
    checkVis=numpy.zeros(n)#訪れたか確認するためのリスト
    checkVinit=numpy.zeros(n)#初期化のためのりすと
    for i in range(n):
        if checkOK[i]==5:
            continue
        checkVis=checkVinit
        Visted=[i]
        checkVis[i]=5
        toVis=queue.Queue()
        
        for j in range(len(root[i])):
            nex=root[i][j]
            if checkVis[j]!=5 and nex==1:
                toVis.put(j)

        while toVis.empty()==False:
        
            now=toVis.get()

            if checkVis[now]==5:
                continue

            Visted.append(now)
            checkVis[now]=5
            for j in range(n):#len(rooot[now]
                nex=root[now][j]
                if nex==1 and checkVis[j]!=5:
                    toVis.put(j)
    
        for j in Visted:
            OK[j]=Visted
            checkOK[j]=5
    ans=[]
    for i in range(n):
        num=0
        for value in OK[i]:
            if root[i][value]==0:
                num+=1
        ans.append(num)
    print(" ".join(map(str,ans)))
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
import numpy
def main():
    n,m,k=map(int,input().split())
    root=numpy.array([[0]*n for i in range(n)])
    for i in range(n):
        root[i][i]=2
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1][b-1]=1
        root[b-1][a-1]=1
    for i in range(k):
        a,b=map(int,input().split())
        root[a-1][b-1]=-100
        root[b-1][a-1]=-100
    toVis=queue.Queue()
    Visted=[]
    checkOK=numpy.zeros(n)#その点に関しての友達候補つくり済みかどうか
    OK={}#友達候補リスト
    checkVis=numpy.zeros(n)#訪れたか確認するためのリスト
    checkVinit=numpy.zeros(n)#初期化のためのりすと
    for i in range(n):
        if checkOK[i]==5:
            continue
        checkVis=checkVinit
        Visted=[i]
        checkVis[i]=5
        toVis=queue.Queue()
        
        for j in range(len(root[i])):
            nex=root[i][j]
            if checkVis[j]!=5 and nex==1:
                toVis.put(j)

        while toVis.empty()==False:
        
            now=toVis.get()

            if checkVis[now]==5:
                continue

            Visted.append(now)
            checkVis[now]=5
            for j in range(n):#len(rooot[now]
                nex=root[now][j]
                if nex==1 and checkVis[j]!=5:
                    toVis.put(j)
    
        for j in Visted:
            OK[j]=Visted
            checkOK[j]=5
    ans=[]
    for i in range(n):
        num=0
        for value in OK[i]:
            if root[i][value]==0:
                num+=1
        ans.append(num)
    print(" ".join(map(str,ans)))
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
def main():
    n,m,k=map(int,input().split())
    root=[[0]*n for i in range(n)]
    for i in range(n):
        root[i][i]=2
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1][b-1]=1
        root[b-1][a-1]=1
    for i in range(k):
        a,b=map(int,input().split())
        root[a-1][b-1]=-float("inf")
        root[b-1][a-1]=-float("inf")
    toVis=queue.Queue()
    Visted=[]
    
    checkOK=[0]*n
    OK={}
    checkVis=[0]*n
    checkVinit=[0]*n
    for i in range(n):
        if checkOK[i]==5:
            continue
        checkVis=checkVinit
        Visted=[i]
        checkVis[i]=5
        toVis=queue.Queue()
        
        for j in range(len(root[i])):
            nex=root[i][j]
            if checkVis[j]!=5 and nex==1:
                toVis.put(j)

        while toVis.empty()==False:
        
            now=toVis.get()

            if checkVis[now]==5:
                continue

            Visted.append(now)
            checkVis[now]=5
            for j in range(n):#len(rooot[now]
                nex=root[now][j]
                if nex==1 and checkVis[j]!=5:
                    toVis.put(j)
    
        for j in Visted:
            OK[j]=Visted
            checkOK[j]=5
    ans=[]
    for i in range(n):
        num=0
        for value in OK[i]:
            if root[i][value]==0:
                num+=1
        ans.append(num)
    print(" ".join(map(str,ans)))
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
def main():
    n,m,k=map(int,input().split())
    root=[[0]*n for i in range(n)]
    for i in range(n):
        root[i][i]=2
    #print(root)
    for i in range(m):
        a,b=map(int,input().split())
    # print("berfot",root[a-1][b-1])
        root[a-1][b-1]=1
        root[b-1][a-1]=1
    #  print("after",root[a-1][b-1])
    for i in range(k):
        a,b=map(int,input().split())
    #   print(a,b)
        root[a-1][b-1]=-float("inf")
        root[b-1][a-1]=-float("inf")
    #print(root)
    toVis=queue.Queue()
    Visted=[]
    #checkVinit=[0 for i in range(n)]
    
    checkOK=[0]*n
    OK={}
    checkVis=[0]*n
    checkVinit=[0]*n
    for i in range(n):
        if checkOK[i]==5:
            continue
        checkVis=checkVinit
        Visted=[i]
        checkVis[i]=5


        #if checkOK[i]==5:
         #   continue
        toVis=queue.Queue()
        
        for j in range(len(root[i])):
            nex=root[i][j]
        # if j not in Visted and nex==1:
            if checkVis[j]!=5 and nex==1:
                toVis.put(j)

        while toVis.empty()==False:
        
            now=toVis.get()
            #if now in Visted:
            if checkVis[now]==5:
                continue
        #   print("now :" ,now)
            Visted.append(now)
            checkVis[now]=5
            for j in range(n):#len(rooot[now]
                nex=root[now][j]
                #if nex==1 and j not in Visted:
                if nex==1 and checkVis[j]!=5:
        #          print("apend",nex)
                    toVis.put(j)
    
        for j in Visted:
            OK[j]=Visted
            checkOK[j]=5
    #print(OK)
    ans=[]
    for i in range(n):
        num=0
        for value in OK[i]:
            if root[i][value]==0:
                num+=1
        ans.append(num)
    print(" ".join(map(str,ans)))
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
def main():
    n,m,k=map(int,input().split())
    root=[[0]*n for i in range(n)]
    for i in range(n):
        root[i][i]=2
    #print(root)
    for i in range(m):
        a,b=map(int,input().split())
    # print("berfot",root[a-1][b-1])
        root[a-1][b-1]=1
        root[b-1][a-1]=1
    #  print("after",root[a-1][b-1])
    for i in range(k):
        a,b=map(int,input().split())
    #   print(a,b)
        root[a-1][b-1]=-float("inf")
        root[b-1][a-1]=-float("inf")
    #print(root)
    toVis=queue.Queue()
    Visted=[]
    #checkVinit=[0 for i in range(n)]
    
    checkOK=[0]*n
    OK={}
    checkVis=[0]*n
    checkVinit=[0]*n
    for i in range(n):
        checkVis=checkVinit
        Visted=[i]
        checkVis[i]=5


        if checkOK[i]==5:
            continue
        toVis=queue.Queue()
        
        for j in range(len(root[i])):
            nex=root[i][j]
        # if j not in Visted and nex==1:
            if checkVis[j]!=5 and nex==1:
                toVis.put(j)

        while toVis.empty()==False:
        
            now=toVis.get()
            #if now in Visted:
            if checkVis[now]==5:
                continue
        #   print("now :" ,now)
            Visted.append(now)
            checkVis[now]=5
            for j in range(n):#len(rooot[now]
                nex=root[now][j]
                #if nex==1 and j not in Visted:
                if nex==1 and checkVis[j]!=5:
        #          print("apend",nex)
                    toVis.put(j)
    
        for j in Visted:
            OK[j]=Visted
            checkOK[j]=5
    #print(OK)
    ans=[]
    for i in range(n):
        num=0
        for value in OK[i]:
            if root[i][value]==0:
                num+=1
        ans.append(num)
    print(" ".join(map(str,ans)))
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
def main():
    n,m,k=map(int,input().split())
    root=[[0]*n for i in range(n)]
    for i in range(n):
        root[i][i]=2
    #print(root)
    for i in range(m):
        a,b=map(int,input().split())
    # print("berfot",root[a-1][b-1])
        root[a-1][b-1]=1
        root[b-1][a-1]=1
    #  print("after",root[a-1][b-1])
    for i in range(k):
        a,b=map(int,input().split())
    #   print(a,b)
        root[a-1][b-1]=-float("inf")
        root[b-1][a-1]=-float("inf")
    #print(root)
    toVis=queue.Queue()
    Visted=[]
    checkOK=[0 for i in range(n)]
    OK={}
    checkVis=[0 for i in range(n)]
    checkVinit=checkVis
    for i in range(n):
        checkVis=checkVinit
        Visted=[i]
        checkVis[i]=5


        if checkOK[i]==5:
            continue
        toVis=queue.Queue()
        
        for j in range(len(root[i])):
            nex=root[i][j]
        # if j not in Visted and nex==1:
            if checkVis[j]!=5 and nex==1:
                toVis.put(j)

        while toVis.empty()==False:
        
            now=toVis.get()
            #if now in Visted:
            if checkVis[now]==5:
                continue
        #   print("now :" ,now)
            Visted.append(now)
            checkVis[now]=5
            for j in range(n):#len(rooot[now]
                nex=root[now][j]
                #if nex==1 and j not in Visted:
                if nex==1 and checkVis[j]!=5:
        #          print("apend",nex)
                    toVis.put(j)
    
        for j in Visted:
            OK[j]=Visted
            checkOK[j]=5
    #print(OK)
    ans=[]
    for i in range(n):
        num=0
        for value in OK[i]:
            if root[i][value]==0:
                num+=1
        ans.append(num)
    print(" ".join(map(str,ans)))
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
n,m,k=map(int,input().split())
root=[[0]*n for i in range(n)]
for i in range(n):
    root[i][i]=2
#print(root)
for i in range(m):
    a,b=map(int,input().split())
   # print("berfot",root[a-1][b-1])
    root[a-1][b-1]=1
    root[b-1][a-1]=1
  #  print("after",root[a-1][b-1])
for i in range(k):
    a,b=map(int,input().split())
 #   print(a,b)
    root[a-1][b-1]=-float("inf")
    root[b-1][a-1]=-float("inf")
#print(root)
toVis=queue.Queue()
Visted=[]
checkOK=[0 for i in range(n)]
OK={}
checkVis=[0 for i in range(n)]
checkVinit=checkVis
for i in range(n):
    checkVis=checkVinit
    Visted=[i]
    checkVis[i]=5


    if checkOK[i]==5:
        continue
    toVis=queue.Queue()
    
    for j in range(len(root[i])):
        nex=root[i][j]
       # if j not in Visted and nex==1:
        if checkVis[j]!=5 and nex==1:
            toVis.put(j)

    while toVis.empty()==False:
    
        now=toVis.get()
        #if now in Visted:
        if checkVis[now]==5:
            continue
     #   print("now :" ,now)
        Visted.append(now)
        checkVis[now]=5
        for j in range(n):#len(rooot[now]
            nex=root[now][j]
            #if nex==1 and j not in Visted:
            if nex==1 and checkVis[j]!=5:
      #          print("apend",nex)
                toVis.put(j)
   
    for j in Visted:
        OK[j]=Visted
        checkOK[j]=5
#print(OK)
ans=[]
for i in range(n):
    num=0
    for value in OK[i]:
        if root[i][value]==0:
            num+=1
    ans.append(num)
print(" ".join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
import queue
n,m,k=map(int,input().split())
root=[[0]*n for i in range(n)]
for i in range(n):
    root[i][i]=2
#print(root)
for i in range(m):
    a,b=map(int,input().split())
   # print("berfot",root[a-1][b-1])
    root[a-1][b-1]=1
    root[b-1][a-1]=1
  #  print("after",root[a-1][b-1])
for i in range(k):
    a,b=map(int,input().split())
 #   print(a,b)
    root[a-1][b-1]=-float("inf")
    root[b-1][a-1]=-float("inf")
#print(root)
toVis=queue.Queue()
Visted=[]
OK={}
checkVis=[0 for i in range(n)]
checkVinit=checkVis
for i in range(n):
    checkVis=checkVinit
    Visted=[i]
    checkVis[i]=5


    if i in OK.keys():
        continue
    toVis=queue.Queue()
    
    for j in range(len(root[i])):
        nex=root[i][j]
       # if j not in Visted and nex==1:
        if checkVis[j]!=5 and nex==1:
            toVis.put(j)

    while toVis.empty()==False:
    
        now=toVis.get()
        #if now in Visted:
        if checkVis[now]==5:
            continue
     #   print("now :" ,now)
        Visted.append(now)
        checkVis[now]=5
        for j in range(n):#len(rooot[now]
            nex=root[now][j]
            #if nex==1 and j not in Visted:
            if nex==1 and checkVis[j]!=5:
      #          print("apend",nex)
                toVis.put(j)
   
    for j in Visted:
        OK[j]=Visted
#print(OK)
ans=[]
for i in range(n):
    num=0
    for value in OK[i]:
        if root[i][value]==0:
            num+=1
    ans.append(num)
print(" ".join(map(str,ans)))