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:
# 2020-05-22
from collections import deque


def main():
    n, m, k = [int(x) for x in input().split()]
    friends = [set() for _ in range(n)]
    blocks = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        friends[a].add(b)
        friends[b].add(a)
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        blocks[a].add(b)
        blocks[b].add(a)

    ansers = []
    ansers_append = ansers.append
    nets = set()
    visited = set()
    visited_add = visited.add
    for person in range(n):
        if person in visited:
            # Already marked in one of the nets.
            for candidate_net in nets:
                if person in candidate_net:
                    net = candidate_net
                    break
        else:
            stack = deque()
            stack_append = stack.append
            stack_pop = stack.pop
            stack_append(person)
            net = {person}
            net_add = net.add
            while stack:
                new = stack_pop()
                for adj in friends[new]:
                    if adj in net:
                        continue
                    stack_append(adj)
                    net_add(adj)
            nets.add(tuple(net))

        # 友達をたどるとブロック対象に着くことがある。積集合 &。
        ans = len(net) - len(friends[person]) - len(net & blocks[person]) - 1
        ansers_append(ans)
        visited_add(person)
    print(*ansers)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 2020-05-22
from collections import deque


def main():
    n, m, k = [int(x) for x in input().split()]
    friends = [set() for _ in range(n)]
    blocks = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        friends[a].add(b)
        friends[b].add(a)
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        blocks[a].add(b)
        blocks[b].add(a)

    ansers = [0] * n
    for person in range(n):
        stack = deque()
        stack_append = stack.append
        stack_pop = stack.pop
        stack_append(person)
        link = {person}
        link_add = link.add
        while stack:
            new = stack_pop()
            for adj in friends[new]:
                if adj in link:
                    continue
                stack_append(adj)
                link_add(adj)
        # 友達をたどるとブロック対象に着くことがある。積集合 &。
        ans = len(link) - len(friends[person]) - len(link & blocks[person]) - 1
        ansers[person] = ans
    print(*ansers)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 2020-05-22
from collections import deque


def main():
    n, m, k = [int(x) for x in input().split()]
    friends = [set() for _ in range(n)]
    blocks = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        friends[a].add(b)
        friends[b].add(a)
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        blocks[a].add(b)
        blocks[b].add(a)

    ansers = []
    ansers_append = ansers.append
    for person in range(n):
        stack = deque()
        stack_append = stack.append
        stack_pop = stack.pop
        stack_append(person)
        link = {person}
        link_add = link.add
        while stack:
            new = stack_pop()
            for adj in friends[new]:
                if adj in link:
                    continue
                stack_append(adj)
                link_add(adj)
        # 友達をたどるとブロック対象に着くことがある。積集合 &。
        ans = len(link) - len(friends[person]) - len(link & blocks[person]) - 1
        ansers_append(ans)
    print(*ansers)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 2020-05-22
from collections import deque


def main():
    n, m, k = [int(x) for x in input().split()]
    friends = [set() for _ in range(n)]
    blocks = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        friends[a].add(b)
        friends[b].add(a)
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        blocks[a].add(b)
        blocks[b].add(a)

    for person in range(n):
        stack = deque()
        stack_append = stack.append
        stack_pop = stack.pop
        stack_append(person)
        link = {person}
        link_add = link.add
        while stack:
            new = stack_pop()
            for adj in friends[new]:
                if adj in link:
                    continue
                stack_append(adj)
                link_add(adj)
        # 友達をたどるとブロック対象に着くことがある。積集合 &。
        ans = len(link) - len(friends[person]) - len(link & blocks[person]) - 1
        if person == n:
            # last
            print(ans)
        else:
            print(ans, end=' ')
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 2020-05-22
from collections import deque


def main():
    n, m, k = [int(x) for x in input().split()]
    friends = [set() for _ in range(n)]
    blocks = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        friends[a].add(b)
        friends[b].add(a)
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        blocks[a].add(b)
        blocks[b].add(a)

    ansers = []
    ansers_append = ansers.append
    for person in range(n):
        stack = deque()
        stack_append = stack.append
        stack_pop = stack.pop
        stack_append(person)
        link = {person}
        link_add = link.add
        while stack:
            new = stack_pop()
            for adj in friends[new]:
                if adj in link:
                    continue
                stack_append(adj)
                link_add(adj)
        # 友達をたどるとブロック対象に着くことがある。積集合 &。
        ans = len(link) - len(friends[person]) - len(link & blocks[person]) - 1
        ansers_append(ans)

    return ' '.join(str(x) for x in ansers)


if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
# 2020-05-22
from collections import deque


def main():
    n, m, k = [int(x) for x in input().split()]
    friends = [set() for _ in range(n)]
    blocks = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        friends[a].add(b)
        friends[b].add(a)
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        blocks[a].add(b)
        blocks[b].add(a)

    ansers = []
    ansers_append = ansers.append
    for person in range(n):
        stack = deque()
        stack_append = stack.append
        stack_pop = stack.popleft
        stack_append(person)
        link = {person}
        link_add = link.add
        while stack:
            new = stack_pop()
            for adj in friends[new]:
                if adj in link:
                    continue
                stack_append(adj)
                link_add(adj)
        # 友達をたどるとブロック対象に着くことがある。積集合 &。
        ans = len(link) - len(friends[person]) - len(link & blocks[person]) - 1
        ansers_append(ans)

    return ' '.join(str(x) for x in ansers)


if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
# 2020-05-22
from collections import deque


def main():
    n, m, k = [int(x) for x in input().split()]
    friends = [set() for _ in range(n)]
    blocks = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        friends[a].add(b)
        friends[b].add(a)
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        blocks[a].add(b)
        blocks[b].add(a)
    ansers = []
    for person in range(n):
        qu = deque()
        dist = [-1] * n
        qu.append(person)
        dist[person] = 0
        while len(qu) > 0:
            new = qu.pop()
            for adj in friends[new]:
                if dist[adj] != -1:
                    continue
                qu.append(adj)
                dist[adj] = dist[new] + 1

        gen = (i not in blocks[person] and d > 1 for i, d in enumerate(dist))
        ansers.append(sum(gen))

    return ' '.join(str(x) for x in ansers)


if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

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

def DFS(i):
    if i not in done:
        done.add(i)
        circle.add(i)
        for f in F[i]:
            DFS(f)
    else:
        return

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

for f in range(M):
    f1,f2=map(int,input().split())
    F[f1-1].append(f2-1)
    F[f2-1].append(f1-1)
for b in range(K):
    b1,b2=map(int,input().split())
    B[b1-1].append(b2-1)
    B[b2-1].append(b1-1)

Group=[]
circle=set()
done=set()
for i in range(N):
    if i not in done:
        DFS(i)
        Group.append(circle)
        circle=set()

ans=[-1 for _ in range(N)]
for i in range(N):
    for j in range(len(Group)):
        if i in Group[j]:
            ans[i]+=len(Group[j])
            break
    for fr in F[i]:
        if fr in Group[j]:
            ans[i]-=1
    for bl in B[i]:
        if bl in Group[j]:
            ans[i]-=1

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
n, m, k = map(int, input().split())
friends = {i: [] for i in range(1, n + 1)}
blocks = {i: [] for i in range(1, n + 1)}
candidates = {i: [] for i in range(1, n + 1)}
nums = []
for _ in range(m):
    a, b = map(int, input().split())
    friends[a].append(b)
    friends[b].append(a)
for _ in range(k):
    a, b = map(int, input().split())
    blocks[a].append(b)
    blocks[b].append(a)

def dfs(a):
    visited = [0] * n
    visited[a - 1] = 1
    if len(friends[a]) == 0:
        return
    q = copy.deepcopy(friends[a])
    while q:
        next = q.pop()
        visited[next - 1] = 1
        for i in friends[next]:
            if visited[i - 1] == 0:
                q.append(i)
                if i not in friends[a]:
                    candidates[a].append(i)

for i in range(1, n + 1):
    dfs(i)
    b = set(blocks[i])
    c = set(candidates[i])
    nums.append(len((b | c) - b))
print(*nums)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

n,m,k = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]
cd = [list(map(int,input().split())) for _ in range(k)]
fr = [[] for _ in range(n)]
bl = [[] for _ in range(n)]
for a,b in ab:
    fr[a-1].append(b-1)
    fr[b-1].append(a-1)
for c,d in cd:
    bl[c-1].append(d-1)
    bl[d-1].append(c-1)    
q = deque([])
gr = deque([])
checked = [0 for _ in range(n)]
for i in range(n):
    if checked[i] == 1:
        continue
    checked[i] = 1
    q.append(i)
    f = deque([i])
    while q:
        v = q.popleft()
        l = fr[v][:]
        qfr = deque(l)
        while qfr:
            x = qfr.popleft()
            if checked[x] == 0:
                f.append(x)
                checked[x] = 1
                q.append(x)
    gr.append(f)
ans = [0 for _ in range(n)]  
while gr:
    l = gr.popleft()
    ll = copy.deepcopy(l)
    mx = len(l) - 1
    #print(mx)
    while l:
        x = l.popleft()
        cnt = mx
        cnt -= len(fr[x])
        #qbl = bl[x]
        for y in bl[x]:
            #y = qbl.popleft()
            #print(y)
            if y in ll:
                cnt -= 1
        ans[x] = cnt

print(*ans)

#print(fr,bl)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

n,m,k = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]
cd = [list(map(int,input().split())) for _ in range(k)]
fr = [deque([]) for _ in range(n)]
bl = [deque([]) for _ in range(n)]
for a,b in ab:
    fr[a-1].append(b-1)
    fr[b-1].append(a-1)
for c,d in cd:
    bl[c-1].append(d-1)
    bl[d-1].append(c-1)    
q = deque([])
gr = deque([])
checked = [0 for _ in range(n)]
for i in range(n):
    if checked[i] == 1:
        continue
    checked[i] = 1
    q.append(i)
    f = deque([i])
    while q:
        v = q.popleft()
        qfr = copy.deepcopy(fr[v])
        while qfr:
            x = qfr.popleft()
            if checked[x] == 0:
                f.append(x)
                checked[x] = 1
                q.append(x)
    gr.append(f)
ans = [0 for _ in range(n)]  
while gr:
    l = gr.popleft()
    ll = copy.deepcopy(l)
    mx0 = len(l) - 1
    #print(mx0)
    while l:
        x = l.popleft()
        mx = mx0
        mx -= len(fr[x])
        qbl = bl[x]
        while qbl:
            y = qbl.popleft()
            #print(y)
            if y in ll:
                mx -= 1
        ans[x] = mx

print(*ans)

#print(fr,bl)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,m,k = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]
cd = [list(map(int,input().split())) for _ in range(k)]
fr = [[] for _ in range(n)]
bl = [[] for _ in range(n)]
for a,b in ab:
    fr[a-1].append(b-1)
    fr[b-1].append(a-1)
for c,d in cd:
    bl[c-1].append(d-1)
    bl[d-1].append(c-1)    
q = deque([])
gr = []
checked = [0 for _ in range(n)]
for i in range(n):
    if checked[i] == 1:
        continue
    checked[i] = 1
    q.append(i)
    f = [i]
    while q:
        v = q.popleft()
        for x in fr[v]:
            if checked[x] == 0:
                f.append(x)
                checked[x] = 1
                q.append(x)
    gr.append(f)
ans = [0 for _ in range(n)]
for i in range(len(gr)):
    l = gr[i]
    mx0 = len(l) - 1
    #print(mx0)
    for x in l:
        mx = mx0
        mx -=len(fr[x])
        for y in bl[x]:
            if y in l:
                mx -= 1
        ans[x] = mx

print(*ans)

#print(fr,bl)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,m,k = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]
cd = [list(map(int,input().split())) for _ in range(k)]
fr = [[] for _ in range(n)]
bl = [[] for _ in range(n)]
for a,b in ab:
    fr[a-1].append(b-1)
    fr[b-1].append(a-1)
for c,d in cd:
    bl[c-1].append(d-1)
    bl[d-1].append(c-1)    
q = deque([])
gr = []
checked = []
for i in range(n):
    if i in checked:
        continue
    checked.append(i)
    q.append(i)
    f = [i]
    while q:
        v = q.popleft()
        for x in fr[v]:
            if x not in checked:
                f.append(x)
                checked.append(x)
                q.append(x)
    gr.append(f)
ans = [0 for _ in range(n)]
for i in range(len(gr)):
    l = gr[i]
    mx0 = len(l) - 1
    #print(mx0)
    for x in l:
        mx = mx0
        mx -=len(fr[x])
        for y in bl[x]:
            if y in l:
                mx -= 1
        ans[x] = mx

print(*ans)

#print(fr,bl)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,m,k = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]
cd = [list(map(int,input().split())) for _ in range(k)]
fr = [[] for _ in range(n)]
bl = [[] for _ in range(n)]
for a,b in ab:
    fr[a-1].append(b-1)
    fr[b-1].append(a-1)
for c,d in cd:
    bl[c-1].append(d-1)
    bl[d-1].append(c-1)    
q = deque([])
gr = []
checked = []
for i in range(n):
    if i in checked:
        continue
    checked.append(i)
    q.append(i)
    f = [i]
    while q:
        v = q.popleft()
        for x in fr[v]:
            if x not in checked:
                f.append(x)
                checked.append(x)
                q.append(x)
    gr.append(f)
ans = [0 for _ in range(n)]
for i in range(len(gr)):
    l = gr[i]
    mx0 = len(l) - 1
    #print(mx0)
    for x in l:
        mx = mx0
        mx -=len(fr[x])
        for y in bl[x]:
            if y in l:
                mx -= 1
        ans[x] = mx

for x in ans:
    print(x)

#print(fr,bl)

Submission status: Time Limit Exceeded

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)
    
while len(W) != 0:
    w = list(W)
    point = w[0]
    group = []
    group.append(point)
    flag[point] = 1
    p = 0
    while p < len(group):
        now = group[p]            
        if len(FG[now]) != 0:# 友達が1人以上いる場合、友達を集合に加える
            for i in range(len(FG[now])):
                if flag[FG[now][i]] == 0:
                    group.append(FG[now][i])
                    flag[FG[now][i]] = 1
        p += 1
    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: Time Limit Exceeded

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)
point = 1


while point <= N:
    group = []
    if flag[point] == 0:# 集合を探索していない場合
        group.append(point)
        flag[point] = 1
        p = 0
        while p < len(group):
            now = group[p]            
            if len(FG[now]) != 0:# 友達が1人以上いる場合、友達を集合に加える
                for i in range(len(FG[now])):
                    if flag[FG[now][i]] == 0:
                        group.append(FG[now][i])
                        flag[FG[now][i]] = 1
            p += 1
        S = len(group)
        for j in range(S):
            m = group[j]
            FB = set(FG[m] + BG[m])
            SG = set(group)
            fc = list(SG - FB)
            result[m] = len(fc) - 1
    point += 1
            
print(*result[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
cd = [list(map(int, input().split())) for _ in range(K)]

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]
  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if(x == y):
      return 
    if self.root[x] > self.root[y]:
      x, y = y, x
    self.root[x] += self.root[y]
    self.root[y] = x 
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  def Count(self, x): # xが属するグループのサイズを返す
    return -self.root[self.Find_Root(x)]
  def Members(self, x): # xが属するグループに属する要素をリストで返す
    return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
  def Roots(self): # 全ての根の要素をリストで返す
    return [i for i, x in enumerate(self.root) if x < 0]
  def Group_Count(self): # グループの数を返す
    return len(self.Roots())

uf = UnionFind(N+1)
friends = [[0]*(N+1) for _ in range(N+1)]
blocks = [[0]*(N+1) for _ in range(N+1)]
ans = [0]*(N+1)
roots = {i:0 for i in range(1, N+1)}
ad = [0]*(N+1)

for a, b in ab:
  uf.Unite(a, b)
  friends[a][b] = 1
  friends[b][a] = 1
  ad[a] += 1
  ad[b] += 1

for i in range(1, N+1):
  roots[uf.Find_Root(i)] += 1

for c, d in cd:
  if uf.isSameGroup(c, d):
    ad[c] += 1
    ad[d] += 1

for i in range(1, N+1):
  ans[i] = roots[uf.Find_Root(i)]

for i in range(1, N+1):
  print(ans[i]-ad[i]-1, end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.readline
N, M, K = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
cd = [list(map(int, input().split())) for _ in range(K)]

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]
  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if(x == y):
      return 
    if self.root[x] > self.root[y]:
      x, y = y, x
    self.root[x] += self.root[y]
    self.root[y] = x 
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  def Count(self, x): # xが属するグループのサイズを返す
    return -self.root[self.Find_Root(x)]
  def Members(self, x): # xが属するグループに属する要素をリストで返す
    return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
  def Roots(self): # 全ての根の要素をリストで返す
    return [i for i, x in enumerate(self.root) if x < 0]
  def Group_Count(self): # グループの数を返す
    return len(self.Roots())

uf = UnionFind(N+1)
friends = [[0]*(N+1) for _ in range(N+1)]
blocks = [[0]*(N+1) for _ in range(N+1)]
ans = [0]*(N+1)
roots = defaultdict(int)
ad = [0]*(N+1)
for a, b in ab:
  uf.Unite(a, b)
  friends[a][b] = 1
  friends[b][a] = 1
  ad[a] += 1
  ad[b] += 1

for i in range(1, N+1):
  roots[uf.Find_Root(i)] += 1

for c, d in cd:
  if uf.isSameGroup(c, d):
    ad[c] += 1
    ad[d] += 1

for i in range(1, N+1):
  ans[i] = roots[uf.Find_Root(i)]

for i in range(1, N+1):
  print(ans[i]-ad[i]-1, end=" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N, M, K = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
cd = [list(map(int, input().split())) for _ in range(K)]

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]
  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if(x == y):
      return 
    if self.root[x] > self.root[y]:
      x, y = y, x
    self.root[x] += self.root[y]
    self.root[y] = x 
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  def Count(self, x): # xが属するグループのサイズを返す
    return -self.root[self.Find_Root(x)]
  def Members(self, x): # xが属するグループに属する要素をリストで返す
    return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
  def Roots(self): # 全ての根の要素をリストで返す
    return [i for i, x in enumerate(self.root) if x < 0]
  def Group_Count(self): # グループの数を返す
    return len(self.Roots())

uf = UnionFind(N+1)
friends = [[0]*(N+1) for _ in range(N+1)]
blocks = [[0]*(N+1) for _ in range(N+1)]
ans = [0]*(N+1)
roots = defaultdict(int)
ad = [0]*(N+1)
for a, b in ab:
  uf.Unite(a, b)
  friends[a][b] = 1
  friends[b][a] = 1
  ad[a] += 1
  ad[b] += 1

for i in range(1, N+1):
  roots[uf.Find_Root(i)] += 1

for c, d in cd:
  if uf.isSameGroup(c, d):
    ad[c] += 1
    ad[d] += 1

for i in range(1, N+1):
  ans[i] = roots[uf.Find_Root(i)]

for i in range(1, N+1):
  print(ans[i]-ad[i]-1, end=" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque

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

f_set = {tuple(map(int,input().split())) for _ in range(m)}

b_set = {tuple(map(int,input().split())) for _ in range(k)}


friends_counts = {key:[] for key in range(1,n+1)}
blocks_counts = {key:[] for key in range(1,n+1)}

for f in f_set:
    friends_counts[f[0]].append(f[1])
    friends_counts[f[1]].append(f[0])

for b in b_set:
    blocks_counts[b[0]].append(b[1])
    blocks_counts[b[1]].append(b[0])



friends_groups_dict = defaultdict(list)

#dfs
que = deque()
groups_count = 0
checked_dict = {key:0 for key in range(1,n+1)}
#que.appendleft(1)

for i in range(1,n+1):
    if checked_dict[i] == 1:
        continue
    que.appendleft(i)
    checked_dict[i] = 1

    while que:
        x = que.popleft()
        friends_groups_dict[groups_count].append(x)
        for i in range(len(friends_counts[x])):
            if checked_dict[friends_counts[x][i]] == 0:
                que.appendleft(friends_counts[x][i])
            checked_dict[friends_counts[x][i]] = 1

    groups_count += 1


result_list=[0]*n

for i in range(len(friends_groups_dict)):
    mini_list = friends_groups_dict[i]
    for j in range(len(mini_list)):
        result_list[mini_list[j]-1] = len(mini_list) - 1 - len(friends_counts[mini_list[j]])
        
        block_counter_in_minilist = 0

        for k in blocks_counts[mini_list[j]]:
            if k in mini_list:
                block_counter_in_minilist += 1
        
        result_list[mini_list[j]-1] -= block_counter_in_minilist
 
print(" ".join(map(str,result_list)))



#cの配列の解釈が違ったらしい。。。
#f_set = {tuple(map(int,input().split())) for _ in range(m)}
#
#b_set = {tuple(map(int,input().split())) for _ in range(k)}
#
#c_list = [0] * (n-1)
#
#result_dict = {key:0 for key in range(1,n+1)}
#
#for f in f_set:
#    if abs(f[0]-f[1]) == 1:
#        c_list[min(f[0],f[1]) - 1] = 1
#    #ここでelseで飛び石での友達のsetを作ってもよいが、そもそもsetなのでinでの探索にそんなに時間かからないし、いったんこのままやってみる。
#
#for start in range(0,n-2):
#    if c_list[start] == 0:
#        #c[start]が1になるまで飛ばす
#        continue
#
#    for end in range(start+1,n-1):
#        if c_list[end] == 0:
#            #友人同士ではないペアまできたらstartをインクリメント
#            break
#        
#        #もし「友人候補」の候補者が、「友人関係でない」かつ「ブロック関係でない」ことをチェックしている。
#        if not (start+1,end+2) in f_set and not (end+2,start+1) in f_set and not (start+1,end+2) in b_set and not (end+2,start+1) in b_set:
#            result_dict[start+1] += 1
#            result_dict[end+2] += 1
#
#for i in range(1,n+1):
#    print(result_dict[i])
#
#print(c_list)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque

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

f_set = {tuple(map(int,input().split())) for _ in range(m)}

b_set = {tuple(map(int,input().split())) for _ in range(k)}


friends_counts = {key:[] for key in range(1,n+1)}
blocks_counts = {key:[] for key in range(1,n+1)}

for f in f_set:
    friends_counts[f[0]].append(f[1])
    friends_counts[f[1]].append(f[0])

for b in b_set:
    blocks_counts[b[0]].append(b[1])
    blocks_counts[b[1]].append(b[0])



friends_groups_dict = defaultdict(list)

#dfs
que = deque()
groups_count = 0
checked_dict = {key:0 for key in range(1,n+1)}
#que.appendleft(1)

for i in range(1,n+1):
    if checked_dict[i] == 1:
        continue
    que.appendleft(i)
    checked_dict[i] = 1

    while que:
        x = que.popleft()
        friends_groups_dict[groups_count].append(x)
        for i in range(len(friends_counts[x])):
            if checked_dict[friends_counts[x][i]] == 0:
                que.appendleft(friends_counts[x][i])
            checked_dict[friends_counts[x][i]] = 1

    groups_count += 1


result_list=[0]*n

for i in range(len(friends_groups_dict)):
    mini_list = friends_groups_dict[i]
    for j in range(len(mini_list)):
        result_list[mini_list[j]-1] = len(mini_list) - 1 - len(friends_counts[mini_list[j]])
        
        block_counter_in_minilist = 0

        for k in range(len(blocks_counts[mini_list[j]])):
            if blocks_counts[mini_list[j]][k] in mini_list:
                block_counter_in_minilist += 1
        
        result_list[mini_list[j]-1] -= block_counter_in_minilist
 
print(" ".join(map(str,result_list)))



#cの配列の解釈が違ったらしい。。。
#f_set = {tuple(map(int,input().split())) for _ in range(m)}
#
#b_set = {tuple(map(int,input().split())) for _ in range(k)}
#
#c_list = [0] * (n-1)
#
#result_dict = {key:0 for key in range(1,n+1)}
#
#for f in f_set:
#    if abs(f[0]-f[1]) == 1:
#        c_list[min(f[0],f[1]) - 1] = 1
#    #ここでelseで飛び石での友達のsetを作ってもよいが、そもそもsetなのでinでの探索にそんなに時間かからないし、いったんこのままやってみる。
#
#for start in range(0,n-2):
#    if c_list[start] == 0:
#        #c[start]が1になるまで飛ばす
#        continue
#
#    for end in range(start+1,n-1):
#        if c_list[end] == 0:
#            #友人同士ではないペアまできたらstartをインクリメント
#            break
#        
#        #もし「友人候補」の候補者が、「友人関係でない」かつ「ブロック関係でない」ことをチェックしている。
#        if not (start+1,end+2) in f_set and not (end+2,start+1) in f_set and not (start+1,end+2) in b_set and not (end+2,start+1) in b_set:
#            result_dict[start+1] += 1
#            result_dict[end+2] += 1
#
#for i in range(1,n+1):
#    print(result_dict[i])
#
#print(c_list)