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: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

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

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

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

    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.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n, m, k = map(int, input().split())
friend = UnionFind(n)
block = UnionFind(n)
data = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    data[a-1].add(b-1)
    data[b-1].add(a-1)
    friend.union(a-1, b-1)

for _ in range(k):
    a, b = map(int, input().split())
    block.union(a-1, b-1)

for i in range(n):
    kouho = set(friend.members(i))
    si = set(block.members(i))
    print(len(kouho-data[i]-si), end=' ')

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M, K = map(int, input().split())
G1 = [[]  for _ in range(N)]
G2 = [[]  for _ in range(N)]
ans = [0]*N

for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G1[a].append(b)
    G1[b].append(a)
for i in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    G2[c].append(d)
    G2[d].append(c)
#print(G1)
#print(G2)

infinity = float("inf")

d = [infinity]*N

def BFS(s, d):
    queue = deque()
    queue.append(s)
    d[s] = 0
    visited = []
    G3 = []
    while len(queue) != 0:
      u = queue.popleft()
      visited.append(u)
      for v in G2[u]:
        G3.append(v)
      G3.append(u)
      for e in G1[u]:
      	  if d[e] == infinity:  # d[v] == inf
       	      d[e] = d[u]+1
       	      queue.append(e)
    G3.sort()
    for i in range(len(G3)-1):
      if G3[i] == G3[i+1]:
        ans[G3[i]] -= 1

    return visited

for i in range(N):
    if d[i] == infinity:
        visited = BFS(i, d)

        n = len(visited)
        for v in visited:
            ans[v] += n-1


for i in range(N):
  #print(ans[i])
  ans[i] -= len(G1[i])
  print(ans[i])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4 4 1
2 1
1 3
3 2
3 4
4 1"""
        output = """0 1 0 1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5"""
        output = """0 0 0 0 0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """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"""
        output = """1 3 5 4 3 3 3 3 1 0"""
        self.assertIO(input, output)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

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

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

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

    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.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def resolve():
    n, m, k = map(int, input().split())
    u = UnionFind(n)
    d = defaultdict(lambda: [])
    e = defaultdict(lambda: [])
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        u.union(a, b)
        d[a].append(b)
        d[b].append(a)
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        e[a].append(b)
        e[b].append(a)
    ans = [0] * n
    for i, v in u.all_group_members().items():
        for j in v:
            for k in v:
                if k != j and (not k in d[j]) and (not k in e[j]):
                    ans[k] += 1
    print(*ans)


if __name__ == "__main__":
    unittest.main()

Submission status: Wrong Answer

Solution code:
import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(100000)


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: x - 1, map(int, input().split()))


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def functional(N, mod):
    F = [1] * (N + 1)
    for i in range(N):
        F[i + 1] = (i + 1) * F[i] % mod
    return F


def get_parent(P, a):
    if P[a] == a:
        return a
    b = get_parent(P, P[a])
    P[a] = b
    return b


def make_uf(N, A):
    P = [i for i in range(N)]
    for a, b in A:
        pa = get_parent(P, a)
        pb = get_parent(P, b)
        if pa != pb:
            P[a] = b
    return P


def clust(N, P):
    C = []
    for i in range(N):
        for c in C:
            if get_parent(P, i) == get_parent(P, c[0]):
                c.append(i)
                break
        else:
            C.append([i])
    return list(map(C, set))


def make_cluster(N, friend):
    import queue
    C = []
    already = [False] * N
    for i in range(N):
        if already[i]:
            continue
        already[i] = True
        s = {i}
        q = queue.Queue()
        q.put(i)
        while not q.empty():
            k = q.get()
            out = friend[k]
            for l in out:
                if already[l]:
                    continue
                s.add(l)
                q.put(l)
                already[l] = True
        C.append(s)

    return C


def main():
    N, M, K = read_values()

    friend = [set() for _ in range(N)]
    for _ in range(M):
        a, b = read_index()
        friend[a].add(b)
        friend[b].add(a)
    
    block = [set() for _ in range(N)]
    for _ in range(K):
        a, b = read_index()
        block[a].add(b)
        block[b].add(a)


    res = [0] * N
    C = make_cluster(N, friend)
    for c in C:
        for i in c:
            print(i)
            res[i] = len(c.difference(friend[i], block[i], {i}))

    print(" ".join(map(str, res)))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
class UnionFindNode:
    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.rank_ = 1
        self.member_num_ = 1

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()

        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                n_root, child = root, unite_root
            else:
                n_root, child = unite_root, root
            child.parent_ = n_root
            n_root.rank_ = max(n_root.rank_, child.rank_ + 1)
            n_root.member_num_ = n_root.member_num_ + child.member_num_
N, K, L = map(int, input().split())
node_list1 = [UnionFindNode(i) for i in range(N)]
d3 = [0] * N
for _ in range(K):
    a, b = map(int, input().split())
    node_list1[a-1].unite(node_list1[b-1])
    d3[a-1] += 1
    d3[b-1] += 1
    
node_list2 = [UnionFindNode(i) for i in range(N)]
for _ in range(L):
    a, b = map(int, input().split())
    node_list2[a-1].unite(node_list2[b-1])

rs = []
from collections import defaultdict
d = defaultdict(int)
for i in range(N):
    rs.append((node_list1[i].root().group_id_, node_list2[i].root().group_id_))
    d[(node_list1[i].root().group_id_, node_list2[i].root().group_id_)] += 1

rr = []
for i in range(N):
    x = node_list1[i].root().member_num_
    y = d[(node_list1[i].root().group_id_, node_list2[i].root().group_id_)]
    rr.append(x- y- d3[i])
print(*rr)

Submission status: Wrong Answer

Solution code:
n, m, k = map(int, input().split())
ans = [n-1] * n
for i in range(m):
    a, b = map(int, input().split())
    ans[a-1] -= 1
    ans[b-1] -= 1
for i in range(k):
    c, d = map(int, input().split())
    ans[c-1] -= 1
    ans[d-1] -= 1
print(' '.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
n, m, k = map(int, input().split())
res = []
for _ in range(m):
    a, b = map(int, input().split())
    res.append(a)
    res.append(b)
for _ in range(k):
    c, d = map(int, input().split())
    res.append(c)
    res.append(d)
ans = [(n-1)]*n
for i in range(n):
    p = res.count(i+1)
    ans[i] -= p
for i in range(n):
    if ans[i] < 0:
        ans[i] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
#https://note.nkmk.me/python-union-find/
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

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

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

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

    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.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    N,M,K = list(map(int,input().split()))
    counter = Counter()
    uf = UnionFind(N+1)
    for i in range(M):
        a,b = list(map(int,input().split()))
        counter.update((a,b))
        uf.union(a,b)
    
    ans = [0]*(N+1)

    for i in range(1,N+1):
        ans[i] = uf.size(i)-counter[i]-1
    for i in range(K):
        a,b = list(map(int,input().split()))
        if uf.same(a,b):
            ans[a] -= 1
            ans[b] -= 1
    
    for i in range(1,N):
        print(ans[i] if 0<=ans[i] else 0,end=" ")
    print(ans[i] if 0<=ans[i] else 0)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, M, K = map(int, input().split())
friend = [[] for _ in range(N)]
block = [[] for _ in range(N)]
ans = [0] * N

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

def dfs(start, i):
	global visited
	global friend
	global block
	global ans
	visited[i] = 1
	for adj in friend[i]:
		if visited[adj]: continue
		if not adj in friend[start] and not adj in block[start]:
			ans[start] += 1
		return dfs(start, adj)
		
	
for i in range(N):
	visited = [0] * N
	dfs(i, i)
	
print(*ans)

Submission status: Wrong Answer

Solution code:
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)]

friends = {i:set() for i in range(1, N+1)}

for a, b in AB:
    friends[a].add(b)
    friends[b].add(a)

blocks = {i:set() for i in range(1, N+1)}
for c, d in CD:
    blocks[c].add(d)
    blocks[d].add(c)

from collections import deque
areas = {i:set() for i in range(1, N+1)}
visited = set()
for i in range(1, N+1):
    if i in visited:
        continue
    q = deque([i])
    while q:
        p = q.pop()
        for f in friends[p]:
            if f not in areas[i]:
                q.appendleft(f)
                areas[i].add(f)
                visited.add(f)
    for j in areas[i]:
        areas[j] = areas[i]

# print(areas)
ans = []
for i in range(1, N+1):
    ans.append(len(areas[i] - friends[i] - blocks[i]) - 1)
print(*ans)

Submission status: Wrong Answer

Solution code:
n,m,k=map(int,input().split())
ans=[n-1]*n
for i in range(m):
    a,b=map(int,input().split())
    ans[a-1]-=1
    ans[b-1]-=1
for i in range(k):
    c,d=map(int,input().split())
    ans[c-1]-=1
    ans[d-1]-=1
print(*ans)

Submission status: Wrong Answer

Solution code:
import numpy as np


if __name__ == '__main__':
    n, m,k = map(int, input().split())
    friend = []
    for i in range(n):
        friend.append([1]*n)

    for i in range(m):
        b, c = map(int, input().split())
        friend[b-1][c-1] =0
        friend[c-1][b-1] =0

    for i in range(k):
        b, c = map(int, input().split())
        friend[b-1][c-1] =0
        friend[c-1][b-1] =0
    ans = ""
    arr = np.array(friend)

    for i in range(n):
        if ans == "":
            x = np.sum(arr[0])
            ans = str(x -1)
        else:
            ans = ans + " "+str(np.sum(arr[i]) -1)
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
#https://note.nkmk.me/python-union-find/
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

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

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

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

    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.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    N,M,K = list(map(int,input().split()))
    counter = Counter()
    
    friend = [[] for i in range(M)]
    #block = [list(map(int,input().split())) for i in range(K)]
    uf = UnionFind(N+1)
    for i in range(M):
        a,b = list(map(int,input().split()))
        counter.update((a,b))
        uf.union(a,b)
    
    ans = [0]*(N+1)
    print(uf)
    print(counter)
    for i in range(1,N+1):
        ans[i] = uf.size(i)-counter[i]-1
    for i in range(K):
        a,b = list(map(int,input().split()))
        if uf.same(a,b):
            ans[a] -= 1
            ans[b] -= 1
    
    print(*ans[1::],sep=" ")

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np


if __name__ == '__main__':
    n, m,k = map(int, input().split())
    friend = []
    for i in range(n):
        friend.append([1]*n)

    for i in range(m):
        b, c = map(int, input().split())
        friend[b-1][c-1] =0
        friend[c-1][b-1] =0

    for i in range(k):
        b, c = map(int, input().split())
        friend[b-1][c-1] =0
        friend[c-1][b-1] =0
    ans = ""
    arr = np.array(friend)

    for i in range(n):
        if ans == "":
            x = np.sum(arr[0])
            ans = str(x)
        else:
            ans = ans + " "+str(np.sum(arr[i]))
    print(ans)

Submission status: Wrong Answer

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

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

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

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

    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.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

U=UnionFind(n)
friend=[0]*n
block=[0]*n
for _ in range(m):
    a,b=map(int,input().split())
    U.union(a-1,b-1)
    friend[a-1]+=1
    friend[b-1]+=1
ans=[0]*n
for i in range(n):
    ans[i]=U.size(i)-friend[i]-1
for _ in range(k):
    c,d=map(int,input().split())
    if U.parents[c-1]>=0 and U.parents[c-1]==U.parents[d-1]:
        ans[c-1]-=1
        ans[d-1]-=1
print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
def answer():
    n, m, k = map(int, input().split())
    friend = defaultdict(set)
    block = defaultdict(set)
    result = defaultdict(set)
    for i in range(m):
        a, b = map(int, input().split())
        friend[a].add(b)
        friend[b].add(a)
    for j in range(k):
        c, d = map(int, input().split())
        block[c].add(d)
        block[d].add(c)
    for i in range(1, n+1):
        done = set()
        q = [i]
        while q:
            p = q.pop()
            if p in done or p in block[i]:
                done.add(p)
                continue
            q += list(friend[p])
            if p not in friend[i] and p != i:
                result[i].add(p)
            done.add(p)
    return ' '.join(str(len(result[i])) for i in range(1, n+1))

print(answer())

Submission status: Wrong Answer

Solution code:
N, M, K = list(map(int, input().split()))

maze = []
for i in range(N):
    row = [0] * N
    row[i] = 1
    maze.append(row)

for i in range(M):
    a, b = list(map(int, input().split()))
    maze[a-1][b-1] = 1
    maze[b-1][a-1] = 1

for i in range(K):
    c, d = list(map(int, input().split()))
    maze[c-1][d-1] = 2
    maze[d-1][c-1] = 2


for row in maze:
    print(row.count(0), end=' ')

Submission status: Wrong Answer

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

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

    friends = [[False] * N for _ in range(N)]
    print(friends)

    for _ in range(M):
        A, B = map(int,input().split())
        friends[A-1][B-1] = True
        friends[B-1][A-1] = True

    print(friends)
    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class UnionFind:
    def __init__(self, n):
        self.state = [-1] * n
        # self.size_table = [1] * n
        # cntはグループ数
        # self.cnt = n

    def root(self, u):
        v = self.state[u]
        if v < 0: return u
        self.state[u] = res = self.root(v)
        return res

    def merge(self, u, v):
        ru = self.root(u)
        rv = self.root(v)
        if ru == rv: return
        du = self.state[ru]
        dv = self.state[rv]
        if du > dv: ru, rv = rv, ru
        if du == dv: self.state[ru] -= 1
        self.state[rv] = ru
        # self.cnt -= 1
        # self.size_table[ru] += self.size_table[rv]
        return

def main():
    n, m, k = MI()
    fb = [set() for _ in range(n)]
    uf = UnionFind(n)
    for _ in range(m):
        a, b = MI1()
        uf.merge(a, b)
        fb[a].add(b)
        fb[b].add(a)
    for _ in range(k):
        a, b = MI1()
        fb[a].add(b)
        fb[b].add(a)
    # print(uf.state)
    ss = defaultdict(set)
    for i in range(n):
        r = uf.state[i]
        if r < 0: ss[i].add(i)
        else: ss[r].add(i)
    # print(ss)
    ans = [0] * n
    for k, v in ss.items():
        for i in v:
            ans[i] = len(v - fb[i]) - 1
    print(*ans)

main()

Submission status: Time Limit Exceeded

Solution code:
class UFNode:
    def __init__(self, ID):
        self.ID = ID
        self.parent = None
        # size of connected component
        self.cc_size = 1

class UFTree:
    def __init__(self, N):
        self.N = N
        self.nodes = [ UFNode(i) for i in range(N) ]

    def get_root(self, node):
        if node.parent is None:
            return node
        root = self.get_root(node.parent)
        node.parent = root
        return root

    def same(self, node1, node2):
        root1 = self.get_root(node1)
        root2 = self.get_root(node2)
        return root1.ID == root2.ID

    def merge(self, node1, node2):
        root1 = self.get_root(node1)
        root2 = self.get_root(node2)

        if root1.ID == root2.ID:
            return

        if root1.cc_size <= root2.cc_size:
            root1.parent = root2
            root2.cc_size += root1.cc_size
        else:
            root2.parent = root1
            root1.cc_size += root2.cc_size

    def get_cc_size(self, node):
        root = self.get_root(node)
        return root.cc_size

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

    friend_list = [set([]) for i in range(N) ]
    block_list = [set([]) for i in range (N)]

    tree = UFTree(N)

    # friend
    for i in range(M):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        friend_list[a].add(b)
        friend_list[b].add(a)
        tree.merge(tree.nodes[a], tree.nodes[b])

    # blocked
    for i in range(K):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        if not tree.same(tree.nodes[a], tree.nodes[b]):
            continue

        # 同じ連結成分であれば後の排除処理のためにリストに追加する
        block_list[a].add(b)
        block_list[b].add(a)

    result = ""
    for i in range(N):
        n = tree.nodes[i]
        result += str(tree.get_cc_size(n) - (len(friend_list[i]) + len(block_list[i]) + 1)) + " "

    print(result[:-1])

main()

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
N, M, K = map(int, input().split())
F = [[] for _ in range(N+1)]
B = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    F[a].append(b)
    F[b].append(a)

for _ in range(K):
    c, d = map(int, input().split())
    B[c].append(d)
    B[d].append(c)

checked = [False] * (N+1)
checked[0] = True
ans = ['0'] * (N+1)
for v in range(1, N+1):
    if checked[v]:
        continue
    A = []
    q = Queue()
    for u in F[v]:
        q.put(u)

    while not q.empty():
        u = q.get()
        if checked[u]: continue
        A.append(u)
        for w in F[u]:
            q.put(w)
        checked[u] = True
    
    for a in A:
        ans[a] = str(len(A)-len(F[a])-1 - len(set(A)&set(B[a])))
    
    checked[v] = True

print(' '.join(ans[1:]))

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
N, M, K = map(int, input().split())
F = [set([]) for _ in range(N+1)]
B = [set([]) for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    F[a].add(b)
    F[b].add(a)

for _ in range(K):
    c, d = map(int, input().split())
    B[c].add(d)
    B[d].add(c)

checked = [False] * (N+1)
checked[0] = True
ans = ['0'] * (N+1)
for v in range(1, N+1):
    if checked[v]:
        continue
    A = []
    q = Queue()
    for u in F[v]:
        q.put(u)

    while not q.empty():
        u = q.get()
        if checked[u]: continue
        A.append(u)
        for w in F[u]:
            q.put(w)
        checked[u] = True
    
    for a in A:
        ans[a] = str(len(set(A) - set(B[a]) - set(F[a]) - set([a])))
    
    checked[v] = True

print(' '.join(ans[1:]))

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
N, M, K = map(int, input().split())
F = [set([]) for _ in range(N+1)]
B = [set([]) for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    F[a].add(b)
    F[b].add(a)

for _ in range(K):
    c, d = map(int, input().split())
    B[c].add(d)
    B[d].add(c)

checked = [False] * (N+1)
checked[0] = True
ans = ['0'] * (N+1)
for v in range(1, N+1):
    if checked[v]:
        continue
    A = []
    q = Queue()
    for u in F[v]:
        q.put(u)

    while not q.empty():
        u = q.get()
        if not checked[u]:
            A.append(u)
            for w in F[u]:
                q.put(w)
            checked[u] = True
    
    for a in A:
        ans[a] = str(len(set(A) - set(B[a]) - set(F[a]) - set([a])))
    
    checked[v] = True

print(' '.join(ans[1:]))

Submission status: Time Limit Exceeded

Solution code:
n,m,k = map(int,input().split())
par = []
for i in range(n):
    par.append(i)  #初期親
rank = [1 for i in range(n)] #初期ランク
flist = [[] for i in range(n)]
blist = [[] for i in range(n)]
cut = []
def find(n): #親検索andランク短縮
    global cut
    if par[n] == n:
        for i in range(len(cut)):
            par[cut[i]] = n
        cut = []
        return n
    else:
        cut.append(n)
        find(par[n])
        return find(par[n])
def shorten(n): # ランクを2にする
    global cut
    if par[n] == n:
        for i in range(len(cut)):
            par[cut[i]] = n
        cut = []
    else:
        cut.append(n)
        shorten(par[n])
def unite(a,b): #グループ併合
    x = find(a)
    y = find(b) #根っこ同士をくっつける
    if x == y: 
        return    #既に同一ユニオンなら何もしない
    if rank[x] < rank[y]:
        par[x] = y 
    elif rank[x] == rank[y]:
        par[y] = x
        rank[x] += 1
    else:
        par[y] = x
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    flist[a].append(b)
    flist[b].append(a)
    unite(a,b)
for i in range(n):
    shorten(i)
for i in range(k):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    if par[a] == par[b]:
        blist[a].append(b)
        blist[b].append(a)
for i in range(n):
    ans = par.count(par[i]) -len(flist[i])-len(blist[i])-1
    print(ans,end = ' ')

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict as dd
sys.setrecursionlimit(10**8)

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

def union(a,b):
    a=find(a)
    b=find(b)
    if a==b:
        return
    
    if rank[a]<rank[b]:
        par[a]=b
        rank[b]+=rank[a]
    else:
        par[b]=a
        rank[a]+=rank[b]       
    return
 

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

par=(list(range(N+1))) ##union-findの親リスト
rank=[1]*(N+1) #unionの大きさ

p=[0]*(N+1) ##枝の数
for _ in range(M):
    A,B=map(int, input().split())
    p[A]+=1
    p[B]+=1
    union(A,B)
for i in range(1,N+1):
    par[i]=find(i)  ##union-find最終まとめ

fd=[[] for i in range(N+1)]
for _ in range(K):
    C,D=map(int, input().split())
    fd[C].append(D)  ##ブロック関係をメモ
    fd[D].append(C)

ans=[0]*(N)
for i in range(1,N+1):
    ans[i-1]=par.count(par[i])-p[i]-1  ##自分と親が同じ数-枝-自分
    for j in fd[i]:
        if par[i]==par[j]:
           ans[i-1]-=1  ##ブロック関係分を削除
print(' '.join(map(str,ans)))