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:
from collections import deque

def Connected_Component(A,N):
    T={i:False for i in range(1,N+1)}
    V=set([i for i in range(1,N+1)])
    C=[]
    p=0
    while p<N:
        v=V.pop()
        S=deque([v])
        T[v]=True
        q=1
        D=[]
        while S:
            w=S.pop()
            D.append(w)
            for u in [u for u in A[w] if not T[u]]:
                q+=1
                T[u]=True
                S.append(u)

        p+=q
        E=set(D)
        C.append(E)
        V-=E
    return C
    
N,M,K=map(int,input().split())
A={i:set() for i in range(1,N+1)}
for _ in range(M):
    a,b=map(int,input().split())
    A[a].add(b)
    A[b].add(a)

C={i:set() for i in range(1,N+1)}
for _ in range(K):
    c,d=map(int,input().split())
    C[c].add(d)
    C[d].add(c)

E=Connected_Component(A,N)
F=["*"]+[0]*(N)
for i in range(len(E)):
    for x in E[i]:
        F[x]=i
P=[]
for i in range(1,N+1):
    c=F[i]
    P.append(str(len(E[c]-(A[i]|C[i]|{i}))))
print(" ".join(P))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
    
N,M,K=map(int,input().split())
A={i:set() for i in range(1,N+1)}
for _ in range(M):
    a,b=map(int,input().split())
    A[a].add(b)
    A[b].add(a)

C={i:set() for i in range(1,N+1)}
for _ in range(K):
    c,d=map(int,input().split())
    C[c].add(d)
    C[d].add(c)

T={i:False for i in range(1,N+1)}
V=set([i for i in range(1,N+1)])
E=[]
p=0
while p<N:
    v=V.pop()
    S=deque([v])
    T[v]=True
    p+=1
    D=[]
    while S:
        w=S.pop()
        D.append(w)
        for u in [u for u in A[w] if not T[u]]:
            p+=1
            T[u]=True
            S.append(u)
    E.append(set(D))
    V-=set(D)

        
F=["*"]+[0]*(N)
for i in range(len(E)):
    for x in E[i]:
        F[x]=i

for i in range(1,N+1):
    c=F[i]
    print(len(E[c]-(A[i]|C[i]|{i})),end="")
    if i!=N:
        print(" ",end="")
print()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**5+200)

def Connected_Component(A,N):
    T={i:False for i in range(1,N+1)}
    V=set([i for i in range(1,N+1)])
    C=[]
    p=0
    while p<N:
        v=V.pop()
        S=deque([v])
        T[v]=True
        q=1
        D=[]
        while S:
            w=S.pop()
            D.append(w)
            for u in [u for u in A[w] if not T[u]]:
                q+=1
                T[u]=True
                S.append(u)

        p+=q
        E=set(D)
        C.append(E)
        V-=E
    return C
    
N,M,K=map(int,input().split())
A={i:set() for i in range(1,N+1)}
for _ in range(M):
    a,b=map(int,input().split())
    A[a].add(b)
    A[b].add(a)

C={i:set() for i in range(1,N+1)}
for _ in range(K):
    c,d=map(int,input().split())
    C[c].add(d)
    C[d].add(c)

E=Connected_Component(A,N)
F=["*"]+[0]*(N)
for i in range(len(E)):
    for x in E[i]:
        F[x]=i

for i in range(1,N+1):
    c=F[i]
    print(len(E[c]-(A[i]|C[i]|{i})),end="")
    if i!=N:
        print(" ",end="")
print()

Submission status: Time Limit Exceeded

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

def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x,y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True
    
def same(x,y):
    return find(x) == find(y)

def size(x):
    return -par[find(x)]


n,m,k = map(int,input().split())
ab = [list(map(int,input().split()))for i in range(m)]
cd = [list(map(int,input().split()))for i in range(k)]

par = [-1]*(n+1)
for i in range(m):
    unite(ab[i][0],ab[i][1])

ablist = [set()for i in range(1+n)]
cdlist = [set()for i in range(n+1)]
for elem in ab:
    ablist[elem[0]].add(elem[1])
    ablist[elem[1]].add(elem[0])
for elem in cd:
    cdlist[elem[0]].add(elem[1])
    cdlist[elem[1]].add(elem[0])

all = set(range(1,n+1))
anslist = []
for i in range(1,n+1):
    cand = list(all-ablist[i]-cdlist[i]-{i})
    c = 0
    for j in range(len(cand)):
        if same(i,cand[j]):
            c += 1
    anslist.append(c)

for ans in anslist:
    print(ans, end = " ")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

def dfs(x, seen):
  seen.add(x)
  for i in G[x]:
    if i in seen:
      continue
    dfs(i, seen)

N, M, K = map(int, input().split())

S = set()
G = [[] for i in range(N)]
for _ in range(M):
  A, B = map(int, input().split())
  A -= 1
  B -= 1
  G[A].append(B)
  G[B].append(A)
  S.add(A)
  S.add(B)

R = []
while len(S) != 0:
    seen = set()
    dfs(S.pop(), seen)
    R.append(seen)
    S = S - seen

Block = [set() for i in range(N)]
for _ in range(K):
  C, D = map(int, input().split())
  Block[C-1].add(D-1)
  Block[D-1].add(C-1)

seq = [0]*N

for r in R:
    lr = len(r)
    for j in r:
        seq[j] =  lr - len(G[j]) - len(r&Block[j]) - 1

print(*seq)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 9)
# 深さ優先探索
def dfs(x, seen):
  seen.add(x)
  for i in G[x]:
    if i in seen:
      continue
    dfs(i, seen)

N, M, K = map(int, input().split())

# Graph構造を作らないといけない。
S = set()
G = defaultdict(list)
for _ in range(M):
  A, B = map(int, input().split())
  G[A-1].append(B-1)
  G[B-1].append(A-1)
  S |= set([A-1, B-1])

n_iter = 0
R = defaultdict(set)
while len(S) != 0:
    seen = set()
    dfs(S.pop(), seen)
    R[n_iter] = seen
    S = S - seen
    n_iter += 1

Block = defaultdict(set)
for _ in range(K):
  C, D = map(int, input().split())
  Block[C-1] |= set([D-1])
  Block[D-1] |= set([C-1])

seq = [0]*N

for i in range(n_iter):
    r = R[i]
    for j in r:
        seq[j] = len(r) - len(G[j]) - len(r&Block[j]) - 1

print(*seq)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**7)

def dfs(x):
    if seen[x-1]==0:
        uni[cnt].append(x)
        seen[x-1]=1
        for i in fri[x-1]:
            dfs(i)
    

n,m,k=map(int,input().split())

fri=[[] for i in range(n)]
blk=[[] for i in range(n)]

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

for i in range(k):
    c,d=map(int,input().split())
    blk[c-1].append(d)
    blk[d-1].append(c)


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

uni=[]
cnt=0
for i in range(1,n+1):
    if seen[i-1]==0:
        uni.append([])
        dfs(i)
        cnt+=1

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

for unii in uni:
    for j in unii:
        cj=len(unii)-len(fri[j-1])-len(set(unii)&set(blk[j-1]))-1
        seq[j-1]=cj

print(*seq)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**7)

def dfs(x):
    if seen[x-1]==0:
        uni[cnt].add(x)
        seen[x-1]=1
        for i in fri[x-1]:
            dfs(i)
    

n,m,k=map(int,input().split())

fri=[[] for i in range(n)]
blk=[set() for i in range(n)]

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

for i in range(k):
    c,d=map(int,input().split())
    blk[c-1].add(d)
    blk[d-1].add(c)


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

uni=[]
cnt=0
for i in range(1,n+1):
    if seen[i-1]==0:
        uni.append(set())
        dfs(i)
        cnt+=1

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

for unii in uni:
    for j in unii:
        cj=len(unii)-len(fri[j-1])-len(unii&blk[j-1])-1
        seq[j-1]=cj

print(*seq)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**7)

def dfs(x):
    uni[cnt].append(x)
    seen[x-1]=1
    for i in fri[x-1]:
        if seen[i-1]==0:
            dfs(i)
    

n,m,k=map(int,input().split())

fri=[[] for i in range(n)]
blk=[[] for i in range(n)]

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

for i in range(k):
    c,d=map(int,input().split())
    blk[c-1].append(d)
    blk[d-1].append(c)


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

uni=[]
cnt=0
for i in range(1,n+1):
    if seen[i-1]==0:
        uni.append([])
        dfs(i)
        cnt+=1

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

for unii in uni:
    for j in unii:
        cj=len(unii)-len(fri[j-1])-len(set(unii)&set(blk[j-1]))-1
        seq[j-1]=cj

print(*seq)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**7)

def dfs(x):
    uni[cnt].append(x)
    seen[x-1]=1
    for i in fri[x-1]:
        if seen[i-1]==0:
            dfs(i)
    

n,m,k=map(int,input().split())

fri=[[] for i in range(n)]
blk=[[] for i in range(n)]

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

for i in range(k):
    c,d=map(int,input().split())
    blk[c-1].append(d)
    blk[d-1].append(c)


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

uni=[]
cnt=0
for i in range(1,n+1):
    if seen[i-1]==0:
        uni.append([])
        dfs(i)
        cnt+=1

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

for unii in uni:
    for j in unii:
        cj=len(unii)-len(fri[j-1])-len(set(unii)&set(blk[j-1]))-1
        seq[j-1]=cj

print(*seq)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**7)

def dfs(x):
    if seen[x-1]==0:
        uni[cnt].add(x)
        seen[x-1]=1
        for i in fri[x-1]:
            dfs(i)
    

n,m,k=map(int,input().split())

fri=[[] for i in range(n)]
blk=[set() for i in range(n)]

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

for i in range(k):
    c,d=map(int,input().split())
    blk[c-1].add(d)
    blk[d-1].add(c)


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

uni=[]
cnt=0
for i in range(1,n+1):
    if seen[i-1]==0:
        uni.append(set())
        dfs(i)
        cnt+=1

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

for unii in uni:
    for j in unii:
        cj=len(unii)-len(fri[j-1])-len(unii&blk[j-1])-1
        seq[j-1]=cj

print(*seq)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**7)

def dfs(x):
    if seen[x-1]==0:
        uni[cnt].append(x)
        seen[x-1]=1
        for i in fri[x-1]:
            dfs(i)
    

n,m,k=map(int,input().split())

fri=[[] for i in range(n)]
blk=[[] for i in range(n)]

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

for i in range(k):
    c,d=map(int,input().split())
    blk[c-1].append(d)
    blk[d-1].append(c)


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

uni=[]
cnt=0
for i in range(1,n+1):
    if seen[i-1]==0:
        uni.append([])
        dfs(i)
        cnt+=1

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

for unii in uni:
    for j in unii:
        cj=len(unii)-len(fri[j-1])-1
        for k in blk[j-1]:
            if k in unii:
                cj-=1
        seq[j-1]=cj

s=list(map(str,seq))

s=" ".join(s)

print(s)

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
F = [[] for _ in range(N)]
B = [[] for _ in range(N)]

# フレンドの隣接リスト
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    F[a].append(b)
    F[b].append(a)

# ブロックの隣接リスト
for _ in range(K):
    c, d = map(int, input().split())
    c, d = c - 1, d - 1
    B[c].append(d)
    B[d].append(c)


# 交友関係グループ（辞書型）
D = {}
# グループの親
parent = [-1] * N
# 訪問管理
visited = [False] * N

for root in range(N):
    if visited[root]:
        continue

    D[root] = set([root])
    # 訪問先のスタック
    stack = [root]
    # 訪問先が無くなるまで
    while stack:
        # 訪問者をポップアップ
        n = stack.pop()
        # 訪問者を訪問済み
        visited[n] = True
        # 訪問者のグループの親を設定
        parent[n] = root

        # root のフレンドをグループと訪問先に追加
        for to in F[n]:
            if visited[to]:
                continue
            D[root].add(to)
            stack.append(to)

ans = [0] * N
for iam in range(N):
    # 自分の交友関係グループを設定
    group = D[parent[iam]]
    # グループからフレンドと自分を除く
    tmp_ans = len(group) - len(F[iam]) - 1
    # グループからブロックを除く
    for block in B[iam]:
        if block in group:
            tmp_ans -= 1
    ans[iam] = tmp_ans

print(*ans, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
F = [[] for _ in range(N)]
B = [[] for _ in range(N)]
 
# フレンドの隣接リスト
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    F[a].append(b)
    F[b].append(a)
 
# ブロックの隣接リスト
for _ in range(K):
    c, d = map(int, input().split())
    c, d = c - 1, d - 1
    B[c].append(d)
    B[d].append(c)
 
 
# 交友関係グループ（辞書型）
D = {}
# グループの親
parent = [-1] * N
# 訪問管理
visited = [False] * N
stack = deque()
 
for root in range(N):
    if visited[root]:
        continue
 
    D[root] = set([root])
    # 訪問先のスタック
    stack.append(root)
    # 訪問先が無くなるまで
    while len(stack)>0:
        # 訪問者をポップアップ
        n = stack.popleft()
        if visited[n]:
            continue
        # 訪問者を訪問済み
        visited[n] = True
        # 訪問者のグループの親を設定
        parent[n] = root
 
        # root のフレンドをグループと訪問先に追加
        D[root]=D[root] | set(F[n])
        stack.extend(F[n])
 
ans = [0] * N
for iam in range(N):
    # 自分の交友関係グループを設定
    group = D[parent[iam]]
    # グループからフレンドと自分を除く
    tmp_ans = len(group) - len(F[iam]) - 1
    # グループからブロックを除く
    for block in B[iam]:
        if block in group:
            tmp_ans -= 1
    ans[iam] = tmp_ans
 
print(*ans, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M, K = map(int, input().split())
F = [[] for _ in range(N)]
B = [[] for _ in range(N)]
 
# フレンドの隣接リスト
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    F[a].append(b)
    F[b].append(a)
 
# ブロックの隣接リスト
for _ in range(K):
    c, d = map(int, input().split())
    c, d = c - 1, d - 1
    B[c].append(d)
    B[d].append(c)
 
 
# 交友関係グループ（辞書型）
D = {}
# グループの親
parent = [-1] * N
# 訪問管理
visited = [False] * N
stack = deque()
 
for root in range(N):
    if visited[root]:
        continue
 
    D[root] = set([root])
    # 訪問先のスタック
    stack.append(root)
    # 訪問先が無くなるまで
    while len(stack)>0:
        # 訪問者をポップアップ
        n = stack.pop()
        if visited[n]:
            continue
        # 訪問者を訪問済み
        visited[n] = True
        # 訪問者のグループの親を設定
        parent[n] = root
 
        # root のフレンドをグループと訪問先に追加
        D[root]=D[root] | set(F[n])
        stack.extend(F[n])
 
ans = [0] * N
for iam in range(N):
    # 自分の交友関係グループを設定
    group = D[parent[iam]]
    # グループからフレンドと自分を除く
    tmp_ans = len(group) - len(F[iam]) - 1
    # グループからブロックを除く
    for block in B[iam]:
        if block in group:
            tmp_ans -= 1
    ans[iam] = tmp_ans
 
print(*ans, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
F = [[] for _ in range(N)]
B = [[] for _ in range(N)]
 
# フレンドの隣接リスト
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    F[a].append(b)
    F[b].append(a)
 
# ブロックの隣接リスト
for _ in range(K):
    c, d = map(int, input().split())
    c, d = c - 1, d - 1
    B[c].append(d)
    B[d].append(c)
 
 
# 交友関係グループ（辞書型）
D = {}
# グループの親
parent = [-1] * N
# 訪問管理
visited = [False] * N
 
for root in range(N):
    if visited[root]:
        continue
 
    D[root] = set([root])
    # 訪問先のスタック
    stack = [root]
    # 訪問先が無くなるまで
    while stack:
        # 訪問者をポップアップ
        n = stack.pop()
        if visited[n]:
            continue
        # 訪問者を訪問済み
        visited[n] = True
        # 訪問者のグループの親を設定
        parent[n] = root
 
        # root のフレンドをグループと訪問先に追加
        D[root]=D[root] | set(F[n])
        stack.extend(F[n])
 
ans = [0] * N
for iam in range(N):
    # 自分の交友関係グループを設定
    group = D[parent[iam]]
    # グループからフレンドと自分を除く
    tmp_ans = len(group) - len(F[iam]) - 1
    # グループからブロックを除く
    for block in B[iam]:
        if block in group:
            tmp_ans -= 1
    ans[iam] = tmp_ans
 
print(*ans, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,m,k = map(int,input().split())

cango = [[]for i in range(n)]
cannotgo=[[]for i in range(n)]
for i in range(m):
    a,b = (map(int,input().split()))
    a,b = a-1,b-1
    cango[a].append(b)
    cango[b].append(a)

for i in range(k):
    c,d =(map(int,input().split()))
    c,d = c-1,d-1
    cannotgo[c].append(d)
    cannotgo[d].append(c)
# print(a)
# cango = [[]for i in range(n)]
# for i in a:
#     cango[i[0]-1].append(i[1]-1)
#     cango[i[1]-1].append(i[0]-1)
# print(cango)

# cannotgo=[[]for i in range(n)]
# for i in c:
#     cannotgo[i[0]-1].append(i[1]-1)
#     cannotgo[i[1]-1].append(i[0]-1)
# # print(cannotgo)
alre = [False]*n
parent = [-1]*n
gro = {}
y = deque()
# print(gro)
for i in range(n):
    if alre[i]==True:
        continue
    gro[i]=set([i])
    y.append(i)
    while len(y)>0:
        x = y.popleft()
        alre[x]=True
        parent[x]=i
        for to in cango[x]:
            if alre[to]:
                continue
            # print(to)
            gro[i].add(to)
            y.append(to)
# print(gro)
# print(parent)
ans = [0]*n
# print(ans)
for iam in range(n):
    group = gro[parent[iam]]
    tmp_ans = len(group)-len(cango[iam])-1
    for block in cannotgo[iam]:
        if block in group:
            tmp_ans -=1
    ans[iam]=tmp_ans
print(*ans, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,m,k = map(int,input().split())

cango = [[]for i in range(n)]
cannotgo=[[]for i in range(n)]
for i in range(m):
    a,b = (map(int,input().split()))
    a,b = a-1,b-1
    cango[a].append(b)
    cango[b].append(a)

for i in range(k):
    c,d =(map(int,input().split()))
    c,d = c-1,d-1
    cannotgo[c].append(d)
    cannotgo[d].append(c)
# print(a)
# cango = [[]for i in range(n)]
# for i in a:
#     cango[i[0]-1].append(i[1]-1)
#     cango[i[1]-1].append(i[0]-1)
# print(cango)

# cannotgo=[[]for i in range(n)]
# for i in c:
#     cannotgo[i[0]-1].append(i[1]-1)
#     cannotgo[i[1]-1].append(i[0]-1)
# # print(cannotgo)
alre = [False]*n
parent = [-1]*n
gro = {}

# print(gro)
for i in range(n):
    if alre[i]==True:
        continue
    gro[i]=set([i])
    stack = [i]
    while stack:
        x = stack.pop()
        alre[x]=True
        parent[x]=i
        for to in cango[x]:
            if alre[to]:
                continue
            # print(to)
            gro[i].add(to)
            stack.append(to)
# print(gro)
# print(parent)
ans = [0]*n
# print(ans)
for iam in range(n):
    group = gro[parent[iam]]
    tmp_ans = len(group)-len(cango[iam])-1
    for block in cannotgo[iam]:
        if block in group:
            tmp_ans -=1
    ans[iam]=tmp_ans
print(*ans, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,m,k = map(int,input().split())
a = []
c = []
for i in range(m):
    a.append(list(map(int,input().split())))
for i in range(k):
    c.append(list(map(int,input().split())))
# print(a)
cango = [[]for i in range(n)]
for i in a:
    cango[i[0]-1].append(i[1]-1)
    cango[i[1]-1].append(i[0]-1)
# print(cango)

cannotgo=[[]for i in range(n)]
for i in c:
    cannotgo[i[0]-1].append(i[1]-1)
    cannotgo[i[1]-1].append(i[0]-1)
# print(cannotgo)
alre = [False]*n
parent = [-1]*n
gro = {}

# print(gro)
for i in range(n):
    if alre[i]==True:
        continue
    gro[i]=set([i])
    stack = [i]
    while stack:
        x = stack.pop()
        alre[x]=True
        parent[x]=i
        for to in cango[x]:
            if alre[to]:
                continue
            # print(to)
            gro[i].add(to)
            stack.append(to)
# print(gro)
# print(parent)
ans = [0]*n
# print(ans)
for iam in range(n):
    group = gro[parent[iam]]
    tmp_ans = len(group)-len(cango[iam])-1
    for block in cannotgo[iam]:
        if block in group:
            tmp_ans -=1
    ans[iam]=tmp_ans
print(*ans, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque

class UnionFind():
        def __init__(self, n):
            self.parents = list(range(n))
    
        def find(self, x):
            if self.parents[x] == x:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]
    
        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)
            if x != y:
                self.parents[y] = x

def main():
    N, M, K = map(int, input().split())
    friend_adj = [[] for _ in range(N)]
    block_adj = [[] for _ in range(N)]

    for _ in range(M):
        a, b = map(lambda x: int(x)-1, input().split())
        friend_adj[a].append(b)
        friend_adj[b].append(a)
    for _ in range(K):
        c, d = map(lambda x: int(x)-1, input().split())
        block_adj[c].append(d)
        block_adj[d].append(c)

    ans = [0] * N
    for i in range(N):
        uf = UnionFind(N)
        q = deque([i])
        visited = [-1] * N
        visited[i] = 0
        while q:
            now = q.popleft()
            for v in friend_adj[now]:
                if visited[v] < 0:
                    q.append(v)
                    visited[v] = 0
                    uf.union(now,v)
                    
        # print(uf.parents)
        ans[i] = uf.parents.count(i) - len(friend_adj[i]) - 1
        for b in block_adj[i]:
            if uf.parents[b] == i:
                ans[i] -= 1
    print(*ans)
    
    
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n , m , k = map(int,input().split())
tomo = [set() for i in range(n+1)]
bro = [set() for i in range(n+1)]
for i in range(m):
    a , b = map(int,input().split())
    tomo[a].add(b)
    tomo[b].add(a)
for i in range(k):
    c , d = map(int,input().split())
    bro[c].add(d)
    bro[d].add(c)

visit = [True for i in range(n+1)]
kurasuta = []
for i in range(1,n+1):
    if visit[i]:
        kar = {i}
        d = deque()
        d.append(i)
        visit[i] = False
        while d:
            now = d.popleft()
            for j in tomo[now]:
                if visit[j]:
                    visit[j] = False
                    kar.add(j)
                    d.append(j)
        kurasuta.append(kar)
    else:
        continue
ans = [0 for i in range(n)]

for i in range(len(kurasuta)):
    for j in kurasuta[i]:
        ans[j-1] = len(kurasuta[i] - tomo[j] - bro[j]) - 1

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n , m , k = map(int,input().split())
tomo = [set() for i in range(n+1)]
bro = [set() for i in range(n+1)]
for i in range(m):
    a , b = map(int,input().split())
    tomo[a].add(b)
    tomo[b].add(a)
for i in range(k):
    c , d = map(int,input().split())
    bro[c].add(d)
    bro[d].add(c)

visit = [True for i in range(n+1)]
kurasuta = []
for i in range(1,n+1):
    if visit[i]:
        kar = {i}
        d = deque()
        d.append(i)
        visit[i] = False
        cou = 1
        while d:
            now = d.popleft()
            for j in tomo[now]:
                if visit[j]:
                    cou += 1
                    visit[j] = False
                    kar.add(j)
                    d.append(j)
        kurasuta.append([kar,cou])
    else:
        continue
ans = [0 for i in range(n)]

for i in range(len(kurasuta)):
    for j in kurasuta[i][0]:
        ans[j-1] = len(kurasuta[i][0]- tomo[j] - bro[j]) - 1

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n , m , k = map(int,input().split())
tomo = [set() for i in range(n+1)]
bro = [set() for i in range(n+1)]
for i in range(m):
    a , b = map(int,input().split())
    tomo[a].add(b)
    tomo[b].add(a)
for i in range(k):
    c , d = map(int,input().split())
    bro[c].add(d)
    bro[d].add(c)

visit = [True for i in range(n+1)]
kurasuta = []
for i in range(1,n+1):
    if visit[i]:
        kar = [i]
        d = deque()
        d.append(i)
        visit[i] = False
        cou = 1
        while d:
            now = d.popleft()
            for j in tomo[now]:
                if visit[j]:
                    cou += 1
                    visit[j] = False
                    kar.append(j)
                    d.append(j)
        kurasuta.append([kar,cou])
    else:
        continue
ans = [0 for i in range(n)]

for i in range(len(kurasuta)):
    for j in range(kurasuta[i][1]):
        for k in range(j+1,kurasuta[i][1]):
            if (not kurasuta[i][0][k] in tomo[kurasuta[i][0][j]]) and (not kurasuta[i][0][k] in bro[kurasuta[i][0][j]]):
                ans[kurasuta[i][0][k]-1] += 1
                ans[kurasuta[i][0][j]-1] += 1
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,k = map(int,input().split())
fre_cnt = [0]*n
fre = [[] for i in range(n)]

for i in range(m):
    a,b = map(int,input().split())
    fre[a-1].append(b-1)
    fre[b-1].append(a-1)
    fre_cnt[a-1] += 1
    fre_cnt[b-1] += 1

label = [-1]*n
label_sum = []
def bfs(start,index):
    queue = [start]
    cnt = 1
    while(queue):
        now = queue.pop(0)
        for i in fre[now]:
            if label[i]!=-1:
                continue
            queue.append(i)
            label[i] = index
            cnt += 1
    label_sum.append(cnt)

index = 0
for i in range(n):
    if label[i]!=-1:
        continue
    label[i] = index 
    bfs(i,index)
    index += 1

ans = [0]*n
for i in range(n):
    index = label[i]
    fl = fre_cnt[i]
    ans[i] = label_sum[index] - fl - 1
    
for i in range(k):
    c,d = map(int,input().split())
    if(label[c-1]==label[d-1]):
        ans[c-1] -= 1
        ans[d-1] -= 1
    
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,k = map(int,input().split())
fre_cnt = [0]*n
fre = [[] for i in range(n)]

for i in range(m):
    a,b = map(int,input().split())
    fre[a-1].append(b-1)
    fre[b-1].append(a-1)
    fre_cnt[a-1] += 1
    fre_cnt[b-1] += 1

isSearched = [False]*n
label = [-1]*n
label_sum = []
def bfs(start,index):
    queue = [start]
    cnt = 1
    while(queue):
        now = queue.pop(0)
        for i in fre[now]:
            if isSearched[i]:
                continue
            queue.append(i)
            isSearched[i] = True
            label[i] = index
            cnt += 1
    label_sum.append(cnt)

index = 0
for i in range(n):
    if isSearched[i]:
        continue
    isSearched[i] = True
    label[i] = index 
    bfs(i,index)
    index += 1

ans = [0]*n
for i in range(n):
    index = label[i]
    fl = fre_cnt[i]
    ans[i] = label_sum[index] - fl - 1
    
for i in range(k):
    c,d = map(int,input().split())
    if(label[c-1]==label[d-1]):
        ans[c-1] -= 1
        ans[d-1] -= 1
    
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,k = map(int,input().split())

fre = [[] for i in range(n)]
#blo = [[] for i in range(n)]

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

isSearched = [False]*n
label = [-1]*n
label_sum = []
def bfs(start,index):
    queue = [start]
    cnt = 1
    while(queue):
        now = queue.pop(0)
        for i in fre[now]:
            if isSearched[i]:
                continue
            queue.append(i)
            isSearched[i] = True
            label[i] = index
            cnt += 1
    label_sum.append(cnt)

index = 0
for i in range(n):
    if isSearched[i]:
        continue
    isSearched[i] = True
    label[i] = index 
    bfs(i,index)
    index += 1

ans = [0]*n
for i in range(n):
    index = label[i]
    fl = len(fre[i])
    ans[i] = label_sum[index] - fl - 1
    
for i in range(k):
    c,d = map(int,input().split())
    if(label[c-1]==label[d-1]):
        ans[c-1] -= 1
        ans[d-1] -= 1
    
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        #親要素のノード番号を格納　xが根のとき-(サイズ)を格納
        self.par = [-1 for i in range(n)]
        self.n = n

    def find(self, x):
        #根ならその番号を返す
        if self.par[x] < 0:
            return x
        else:
            #親の親は親
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def is_same(self, x, y):
        #根が同じならTrue
        return self.find(x) == self.find(y)

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

        #木のサイズを比較し、小さいほうから大きいほうへつなぐ
        if self.par[x] > self.par[y]:
            x, y = y, x

        self.par[x] += self.par[y]
        self.par[y] = x

    def size(self, x):
        return -self.par[self.find(x)]

    def members(self, 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.par) 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 __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M, K = map(int, input().split())
graph = [[] for _ in range(N)]
block = [[] for _ in range(N)]
union = UnionFind(N)
for i in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    union.unite(a-1, b-1)
for i in range(K):
    a, b = map(int, input().split())
    block[a-1].append(b-1)
    block[b-1].append(a-1)

for i in range(N):
    ans = len(set(union.members(i)) - set(graph[i]) - set(block[i])) - 1
    print(ans)