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: Runtime Error

Solution code:
import sys
import collections
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(3000)
n,m,k=map(int,input().split())
gf = [[]for i in range(n)]
gb = [[]for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    gf[a-1].append(b-1)
    gf[b-1].append(a-1)

for i in range(k):
    a,b = map(int,input().split())
    gb[a-1].append(b-1)
    gb[b-1].append(a-1)

seen = [0 for i in range(n)]

def dfs(i,k):
    for nec in gf[i]:
        if seen[nec]!=0:
            continue
        seen[nec]=k
        dfs(nec,k)
k=1

for i in range(n):
    if seen[i]==0:
        dfs(i,k)
        k+=1
c = collections.Counter(seen)
lis = []
for i in range(n):
    dec = 0
    for k in gb[i]:
        if seen[i]==seen[k]:
            dec += 1
    lis.append(c[seen[i]]-len(gf[i])-dec-1)
print(*lis)

Submission status: Runtime Error

Solution code:
N, M, K = map(int, input().split())
friend = [list(map(int, input().split())) for i in range(M)]
block = [list(map(int, input().split())) for i in range(K)]
result = []
FG = [[] for i in range(N + 1)]
BG = [[] for i in range(N + 1)]
 
for i in range(M):
    a = friend[i][0]
    b = friend[i][1]
    FG[a].append(b)
    FG[b].append(a)
 
for i in range(K):
    a = block[i][0]
    b = block[i][1]
    BG[a].append(b)
    BG[b].append(a)
    
result = [0] * (N + 1)
flag = [0] * (N + 1)

W = []
for i in range(1,N+1):
    W.append(i)
W = set(W)

def dfs(i):
    if flag[i] == 1:
        return
    else:
        group.append(i)
        flag[i] = 1
        for j in range(len(FG[i])):
            dfs(FG[i][j])
        
while len(W) != 0:
    w = list(W)
    point = w[0]
    group = []
    
    if FG[point] != 0:
        dfs(point)

        S = len(group)
        for j in range(S):
            m = group[j]
            FB = set(FG[m] + BG[m])
            SG = set(group)
            fc = SG - FB
            result[m] = len(fc) - 1
    else:
        flag[point] = 1
        SG = {point}
    W = W - SG
    
            
print(*result[1:])

Submission status: Runtime Error

Solution code:
N, M, K = map(int, input().split())
friend = [list(map(int, input().split())) for i in range(M)]
block = [list(map(int, input().split())) for i in range(K)]

result = []
FG = [[] for i in range(N + 1)]
BG = [[] for i in range(N + 1)]
 
for i in range(M):
    a = friend[i][0]
    b = friend[i][1]
    FG[a].append(b)
    FG[b].append(a)
 
for i in range(K):
    a = block[i][0]
    b = block[i][1]
    BG[a].append(b)
    BG[b].append(a)
    
result = [0] * (N + 1)
flag = [0] * (N + 1)

W = []
for i in range(1,N+1):
    W.append(i)
W = set(W)

def dfs(i):
    if len(FG[i]) == 0 or flag[i] == 1:
        return
    else:
        group.append(i)
        flag[i] = 1
        for j in range(len(FG[i])):
            dfs(FG[i][j])
        
while len(W) != 0:
    w = list(W)
    point = w[0]
    group = []

    dfs(point)

    S = len(group)
    for j in range(S):
        m = group[j]
        FB = set(FG[m] + BG[m])
        SG = set(group)
        fc = SG - FB
        result[m] = len(fc) - 1
    W = W - SG
    
            
print(*result[1:])

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


class UnionFind:
    def __init__(self, n_nodes):
        self.n_nodes = n_nodes

        # self.parents[x] < 0 の時，xが根である．
        # また，xが根の時，(-1) * (同一グループの要素数) が格納されるようになる.
        self.parents = [-1] * n_nodes

    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 = self.find(x)
        y = self.find(y)

        if x == y:
            return

        # 常にxの方が要素数が多くなるように，スワップする
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        # 要素数の少ない方のグループを，要素数が多い方の木に貼る．
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def get_size(self, x):
        return -self.parents[self.find(x)]

    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    def get_members(self, x):
        parent = self.find(x)
        return [i for i in range(self.n_nodes) if self.find(i) == parent]

    def get_parent_list(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def get_n_groups(self):
        return len(self.get_parent_list())

    def get_members_dict(self):
        return {par: self.get_members(par) for par in self.get_parent_list()}


def main():
    N, M, K = map(int, input().split())
    tree = UnionFind(N)

    friends = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        tree.unite(a, b)
        friends[a].append(b)
        friends[b].append(a)

    ng = [[] for _ in range(N)]
    for _ in range(K):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        ng[c].append(d)
        ng[d].append(a)

    ans = []
    for i in range(N):
        n_ng = 0
        for j in ng[i]:
            if tree.is_same(i, j):
                n_ng += 1

        n_member = tree.get_size(i)
        n_friends = len(friends[i])
        # 自分を引くのを忘れない
        ans.append(n_member - n_friends - n_ng - 1)

    print(*ans, sep=" ")


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, m, k = map(int, input().split())
    f = [{i} for i in range(n)]
    g = [set() for _ in range(n)]
    for _ in range(m):
        i, j = map(lambda x: int(x) - 1, input().split())
        f[i].add(j)
        f[j].add(i)
    for _ in range(k):
        i, j = map(lambda x: int(x) - 1, input().split())
        g[i].add(j)
        g[j].add(i)

    vis = [0 for _ in range(n)]
    num = [0 for _ in range(n)]

    def GO_FUCK(i, c):
        fr = f[i]
        for j in fr:
            if not vis[j]:
                vis[j] = 1
                num[j] = c
                grp[-1].add(j)
                GO_FUCK(j, c)

    lb = 0
    grp = []
    for i in range(n):
        if all(vis):
            break
        grp.append(set())
        GO_FUCK(i, lb)
        lb += 1

    for i in range(n):
        gn = num[i]
        gp = grp[gn]
        fc = gp - f[i] - g[i]
        c = len(fc)
        print(c, end=" ")


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, m, k, *abcd = map(lambda x: int(x) - 1, open(0).read().split())
    n += 1
    m += 1
    f = [{i} for i in range(n)]
    g = [set() for _ in range(n)]
    for i, j in zip(*[iter(abcd[:2 * m])] * 2):
        f[i].add(j)
        f[j].add(i)
    for i, j in zip(*[iter(abcd[2 * m:])] * 2):
        g[i].add(j)
        g[j].add(i)

    vis = [0 for _ in range(n)]
    num = [0 for _ in range(n)]

    def GO_FUCK(i, c):
        fr = f[i]
        for j in fr:
            if not vis[j]:
                vis[j] = 1
                num[j] = c
                grp[-1].add(j)
                GO_FUCK(j, c)

    lb = 0
    grp = []
    for i in range(n):
        if all(vis):
            break
        grp.append(set())
        GO_FUCK(i, lb)
        lb += 1

    for i in range(n):
        gn = num[i]
        gp = grp[gn]
        fc = gp - f[i] - g[i]
        c = len(fc)
        print(c, end=" ")


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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: Runtime Error

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: Runtime Error

Solution code:
import queue

import numpy
def main():
    n,m,k=map(int,input().split())
    root=numpy.array([numpy.zeros(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
       # print(i)
        checkVis=checkVinit#訪れたかリストの初期化
        Visted=[i]#iは現在地だ
        checkVis[i]=5#当然訪れている
        toVis=queue.Queue()#訪れるべき点のキュー
        
        for j in range(len(root[i])):#iの列を見て、
            nex=root[i][j]          #i->jの値
            if checkVis[j]!=5 and nex==1:#5は既に訪れている 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(root[now]
                nex=root[now][j]
                if nex==1 and checkVis[j]!=5:#次に訪れることのできる点をキューに入れる
                    toVis.put(j)
    
        for j in Visted:#訪れたリストにある点は互いに行き来ができるはず
            OK[j]=Visted#各点の訪れられる点リストは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: Runtime Error

Solution code:
import queue
import sys
import numpy
input = sys.stdin.readline

def main():
    n,m,k=map(int,input().split())
    root=numpy.array([numpy.zeros(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
       # print(i)
        checkVis=checkVinit#訪れたかリストの初期化
        Visted=[i]#iは現在地だ
        checkVis[i]=5#当然訪れている
        toVis=queue.Queue()#訪れるべき点のキュー
        
        for j in range(len(root[i])):#iの列を見て、
            nex=root[i][j]          #i->jの値
            if checkVis[j]!=5 and nex==1:#5は既に訪れている 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(root[now]
                nex=root[now][j]
                if nex==1 and checkVis[j]!=5:#次に訪れることのできる点をキューに入れる
                    toVis.put(j)
    
        for j in Visted:#訪れたリストにある点は互いに行き来ができるはず
            OK[j]=Visted#各点の訪れられる点リストは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: Runtime Error

Solution code:
import queue
import sys
import numpy
input = sys.stdin.readline

def main():
    n,m,k=map(int,input().split())
    root=numpy.array([numpy.zeros(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
        print(i)
        checkVis=checkVinit#訪れたかリストの初期化
        Visted=[i]#iは現在地だ
        checkVis[i]=5#当然訪れている
        toVis=queue.Queue()#訪れるべき点のキュー
        
        for j in range(len(root[i])):#iの列を見て、
            nex=root[i][j]          #i->jの値
            if checkVis[j]!=5 and nex==1:#5は既に訪れている 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(root[now]
                nex=root[now][j]
                if nex==1 and checkVis[j]!=5:#次に訪れることのできる点をキューに入れる
                    toVis.put(j)
    
        for j in Visted:#訪れたリストにある点は互いに行き来ができるはず
            OK[j]=Visted#各点の訪れられる点リストは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: Runtime Error

Solution code:
import queue
import numpy
def main():
    n,m,k=map(int,input().split())
    root=numpy.array([numpy.zeros(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
        print(i)
        checkVis=checkVinit#訪れたかリストの初期化
        Visted=[i]#iは現在地だ
        checkVis[i]=5#当然訪れている
        toVis=queue.Queue()#訪れるべき点のキュー
        
        for j in range(len(root[i])):#iの列を見て、
            nex=root[i][j]          #i->jの値
            if checkVis[j]!=5 and nex==1:#5は既に訪れている 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(root[now]
                nex=root[now][j]
                if nex==1 and checkVis[j]!=5:#次に訪れることのできる点をキューに入れる
                    toVis.put(j)
    
        for j in Visted:#訪れたリストにある点は互いに行き来ができるはず
            OK[j]=Visted#各点の訪れられる点リストはvistedで共通
            checkOK[j]=5#ｊはもうやらなくていいのでチェック
    print(1," ",1," ",1)
    """
    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: Runtime Error

Solution code:
import queue
import numpy
def main():
    n,m,k=map(int,input().split())
    root=numpy.array([numpy.zeros(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
        print(i)
        checkVis=checkVinit#訪れたかリストの初期化
        Visted=[i]#iは現在地だ
        checkVis[i]=5#当然訪れている
        toVis=queue.Queue()#訪れるべき点のキュー
        
        for j in range(len(root[i])):#iの列を見て、
            nex=root[i][j]          #i->jの値
            if checkVis[j]!=5 and nex==1:#5は既に訪れている 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(root[now]
                nex=root[now][j]
                if nex==1 and checkVis[j]!=5:#次に訪れることのできる点をキューに入れる
                    toVis.put(j)
    
        for j in Visted:#訪れたリストにある点は互いに行き来ができるはず
            OK[j]=Visted#各点の訪れられる点リストはvistedで共通
            checkOK[j]=5#ｊはもうやらなくていいのでチェック
    print(1 1 1 1 1)
    """
    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: Runtime Error

Solution code:
from DataStructures.UnionFind import UnionFind


def main():
    N, M, K = map(int, input().split())
    cnt = [0] * N
    uf = UnionFind(N)

    for _ in range(M):
        A, B = map(lambda x: int(x)-1, input().split())
        cnt[A] += 1
        cnt[B] += 1
        uf.union(A, B)

    for _ in range(K):
        C, D = map(lambda x: int(x)-1, input().split())
        if uf.same(C, D):
            cnt[C] += 1
            cnt[D] += 1

    for i in range(N):
        print(uf.size(i) - cnt[i] - 1, end=" ")


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:

from sys import stdin, setrecursionlimit


def dfs(f, v, seen):
    seen[v] = True

    for nv in f[v]:
        if seen[nv]:
            continue
        dfs(f, nv, seen)


def main():
    n, m, k = map(int, stdin.readline().split())

    f = [[] for _ in range(n)]

    for _ in range(m):
        a, b = map(int, stdin.readline().split())
        f[a - 1].append(b - 1)
        f[b - 1].append(a - 1)

    b = [[] for _ in range(n)]

    for _ in range(k):
        c, d = map(int, stdin.readline().split())
        b[c - 1].append(d - 1)
        b[d - 1].append(c - 1)

    ans = [0] * n

    u = [-1] * n
    uid = 0
    for i in range(n):
        if u[i] == -1:
            seen = [False] * n
            dfs(f, i, seen)
            for j in range(n):
                if seen[j]:
                    u[j] = uid
        uid += 1

    for i in range(n):
        uid = u[i]
        arr = [i for i in range(n) if u[i] == uid]
        tmp = len((set(arr) - set(f[i])) - set(b[i]))
        tmp -= 1
        ans[i] = tmp

    print(*ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit


def dfs(f, v, seen):
    seen[v] = True

    for nv in f[v]:
        if seen[nv]:
            continue
        dfs(f, nv, seen)


def main():
    n, m, k = map(int, stdin.readline().split())

    f = [[] for _ in range(n)]

    for _ in range(m):
        a, b = map(int, stdin.readline().split())
        f[a - 1].append(b - 1)
        f[b - 1].append(a - 1)

    b = [[] for _ in range(n)]

    for _ in range(k):
        c, d = map(int, stdin.readline().split())
        b[c - 1].append(d - 1)
        b[d - 1].append(c - 1)

    ans = [0] * n

    u = [-1] * n
    uid = 0
    for i in range(n):
        if u[i] == -1:
            seen = [False] * n
            dfs(f, i, seen)
            for j in range(n):
                if seen[j]:
                    u[j] = uid
        uid += 1

    for i in range(n):
        uid = u[i]
        arr = [i for i in range(n) if u[i] == uid]
        tmp = len(set(arr) - set(f[i]) - set(b[i]))
        tmp -= 1
        ans[i] = tmp

    print(*ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit


def dfs(f, v, seen):
    seen[v] = True

    for nv in f[v]:
        if seen[nv]:
            continue
        dfs(f, nv, seen)


def main():
    n, m, k = map(int, stdin.readline().split())

    f = [[] for _ in range(n)]

    for _ in range(m):
        a, b = map(int, stdin.readline().split())
        f[a - 1].append(b - 1)
        f[b - 1].append(a - 1)

    b = [[] for _ in range(n)]

    for _ in range(k):
        c, d = map(int, stdin.readline().split())
        b[c - 1].append(d - 1)
        b[d - 1].append(c - 1)

    ans = [0] * n
    for i in range(n):
        seen = [False] * n
        dfs(f, i, seen)
        arr = []
        for j in range(n):
            if seen[j]:
                arr.append(j)
        tmp = len(set(arr) - set(f[i]) - set(b[i]))
        tmp -= 1
        ans[i] = tmp

    print(*ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit


def main():
    n, m, k = map(int, stdin.readline().split())

    f = [[] for _ in range(n)]

    for _ in range(m):
        a, b = map(int, stdin.readline().split())
        f[a - 1].append(b - 1)
        f[b - 1].append(a - 1)

    b = [[] for _ in range(n)]

    for _ in range(k):
        c, d = map(int, stdin.readline().split())
        b[c - 1].append(d - 1)
        b[d - 1].append(c - 1)

    def dfs(v, seen):
        seen[v] = True

        for nv in f[v]:
            if seen[nv]:
                continue
            dfs(nv, seen)

    ans = [0] * n
    for i in range(n):
        seen = [False] * n
        dfs(i, seen)
        arr = []
        for j in range(n):
            if seen[j]:
                arr.append(j)
        tmp = len(set(arr) - set(f[i]) - set(b[i]))
        tmp -= 1
        ans[i] = tmp

    print(*ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Runtime Error

Solution code:
import collections

n,m,k = map(int,raw_input().split(' '))

friendships = [map(int, raw_input().split(' ')) for _ in range(m)]
disses = [map(int, raw_input().split(' ')) for _ in range(k)]

parent = {i:i for i in range(0, n+1)}
sizes = {i:1 for i in range(0, n+1)}

hd = collections.Counter()

adj = collections.defaultdict(set)

def f(parent, u):
	if parent[u] != u: 
		parent[u] = f(parent, parent[u])
	return parent[u]

for a,b in friendships:
	if a != b:
		pa,pb = f(parent, a), f(parent, b)
		
		adj[a].add(b)
		adj[b].add(a)

		if pa != pb:
			parent[pb] = pa
			sizes[pa] += sizes[pb]

for c,d in disses:
	pc,pd = f(parent, c), f(parent, d)
	if (pc == pd):
		hd[c] += 1
		hd[d] += 1
"""
hd[u] = k
u has k disses in its connected component
"""

print ' '.join([str(sizes[f(parent,u)] - len(adj[u]) - hd[u] - 1)  for u in range(1, n+1)])

Submission status: Runtime Error

Solution code:
import collections

n,m,k = map(int,raw_input().split(' '))

friendships = [map(int, raw_input().split(' ')) for _ in range(m)]
disses = [map(int, raw_input().split(' ')) for _ in range(k)]

parent = {i:i for i in range(0, n+1)}
sizes = {i:1 for i in range(0, n+1)}

hd = collections.Counter()

adj = collections.defaultdict(set)

def f(parent, a):
	if parent[a] != a: parent[a] = f(parent, parent[a])
	return parent[a]

for a,b in friendships:
	if a != b:
		pa,pb = f(parent, a), f(parent, b)
		
		adj[a].add(b)
		adj[b].add(a)

		if pa != pb:
			parent[pb] = pa
			sizes[pa] += sizes[pb]

for c,d in disses:
	pa,pb = f(parent, c), f(parent, d)
	if (pa == pb):
		hd[c] += 1
		hd[d] += 1
"""
hd[u] = k
u has k disses in its connected component
"""

print ' '.join([str(sizes[f(parent,u)] - len(adj[u]) - hd[u] - 1)  for u in range(1, n+1)])

Submission status: Runtime Error

Solution code:
import collections

n,m,k = map(int,raw_input().split(' '))

friendships = [map(int, raw_input().split(' ')) for _ in range(m)]
disses = [map(int, raw_input().split(' ')) for _ in range(k)]

parent = {i:i for i in range(1, n+1)}
sizes = {i:1 for i in range(1, n+1)}

hd = collections.Counter()

adj = collections.defaultdict(set)

def f(parent, a):
	if parent[a] != a: parent[a] = f(parent, parent[a])
	return parent[a]

for a,b in friendships:
	if a != b:
		pa,pb = f(parent, a), f(parent, b)
		
		adj[a].add(b)
		adj[b].add(a)

		if pa != pb:
			parent[pb] = pa
			sizes[pa] += sizes[pb]

for c,d in disses:
	pa,pb = f(parent, c), f(parent, d)
	if (d not in adj[c]) and  (pa == pb):
		hd[c] += 1
		hd[d] += 1
"""
hd[u] = k
u has k disses in its connected component
"""

print ' '.join([str(sizes[f(parent,u)] - len(adj[u]) - hd[u] - 1)  for u in range(1, n+1)])

Submission status: Runtime Error

Solution code:
import collections

n,m,k = map(int,raw_input().split(' '))

friendships = [map(int, raw_input().split(' ')) for _ in range(m)]
disses = [map(int, raw_input().split(' ')) for _ in range(k)]

parent = {i:i for i in range(1, n+1)}
sizes = {i:1 for i in range(1, n+1)}

hd = collections.Counter()

adj = collections.defaultdict(set)

def f(parent, a):
	if parent[a] != a: parent[a] = f(parent, parent[a])
	return parent[a]

for a,b in friendships:
	pa,pb = f(parent, a), f(parent, b)
	
	adj[a].add(b)
	adj[b].add(a)

	if pa != pb:
		parent[pb] = pa
		sizes[pa] += sizes[pb]

for c,d in disses:
	pa,pb = f(parent, c), f(parent, d)
	if (d not in adj[c]) and  (pa == pb):
		hd[c] += 1
		hd[d] += 1

print ' '.join([str(sizes[f(parent,u)] - len(adj[u]) - hd[u] - 1)  for u in range(1, n+1)])

Submission status: Runtime Error

Solution code:
import collections

n,m,k = map(int,raw_input().split(' '))

friendships = [map(int, raw_input().split(' ')) for _ in range(m)]
disses = [map(int, raw_input().split(' ')) for _ in range(k)]

parent = {i:i for i in range(1, n+1)}
sizes = {i:1 for i in range(1, n+1)}

hd = collections.Counter()

adj = collections.defaultdict(set)

def f(parent, a):
	if parent[a] != a: parent[a] = f(parent, parent[a])
	return parent[a]

for a,b in friendships:
	pa,pb = f(parent, a), f(parent, b)
	
	adj[a].add(b)
	adj[b].add(a)

	if pa != pb:
		parent[pb] = pa
		sizes[pa] += sizes[pb]

for c,d in disses:
	pa,pb = f(parent, c), f(parent, d)
	if pa == pb:
		hd[c] += 1
		hd[d] += 1

print ' '.join([str(sizes[f(parent,u)] - len(adj[u]) - hd[u] - 1)  for u in range(1, n+1)])