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:
import sys
sys.setrecursionlimit(10**5)

n,m,k=map(int,input().split())
fr=[0 for _ in range(n)]
frl=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    fr[a-1]=fr[a-1]+1
    fr[b-1]=fr[b-1]+1
    frl[a-1].append(b)
    frl[b-1].append(a)

treelist=[]
hitobito=set()

def saiki(c):
    global treelist
    global hitobito
    global frl
    global bll
    global tmpset

    for tsugi in frl[c-1]:
        if not tsugi in hitobito:
            hitobito.add(tsugi)
            tmpset.add(tsugi)
            saiki(tsugi)

for i in range(n):
    tmpset=set()
    saiki(i+1)
    if not tmpset == set():
        treelist.append(tmpset)


bll=[[] for i in range(n)]

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


output=[]
for i in range(n):
    for tree in treelist:
        if i+1 in tree:
            tmpsum=0
            for aaa in frl[i]:
                if aaa in tree:
                    tmpsum+=1
            for bbb in bll[i]:
                if bbb in tree:
                    tmpsum+=1 
            output.extend([str(len(tree)-tmpsum-1)," "])

print("".join(output))

Submission status: Wrong Answer

Solution code:
import collections
import itertools
import operator


class UnionFind:
    def __init__(self, elems=None):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)

        if elems is not None:
            for elem in elems:
                _, _ = self.parent[elem], self.rank[elem]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

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

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]

uf = UnionFind()
N,M,K=map(int,input().split())
A=[];B=[];C=[];D=[]
retu_n=[0]*N
block_n=[0]*N

for m in range(M):
  a,b=map(int,input().split())
  retu_n[a-1] +=1
  retu_n[b-1] +=1
  uf.unite(a,b)
  
  
for k in range(K):
  c,d=map(int,input().split())
  if uf.are_same(c, d):
    block_n[c-1] += 1
    block_n[d-1] += 1
    
  
V=list(uf.grouper())
renketu=[0]*N

for n in range(1,N+1):
  for v in V:
    if n in v:
      renketu[n-1]=len(v)

for n in range(N):
  print(renketu[n]-retu_n[n]-block_n[n]-1, end=" ")

Submission status: Wrong Answer

Solution code:
import collections
import itertools
import operator


class UnionFind:
    def __init__(self, elems=None):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)

        if elems is not None:
            for elem in elems:
                _, _ = self.parent[elem], self.rank[elem]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

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

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]

uf = UnionFind()
N,M,K=map(int,input().split())
A=[];B=[];C=[];D=[]
retu=[[] for _ in range(N)]
block=[[] for _ in range(N)]
block_n=[0]*N

for m in range(M):
  a,b=map(int,input().split())
  A.append(a)
  B.append(b)
  retu[a-1].append(b)
  retu[b-1].append(a)
  uf.unite(a,b)
  
  
for k in range(K):
  c,d=map(int,input().split())
  C.append(c)
  D.append(d)
  block[c-1].append(d)
  block[d-1].append(c)
  if uf.are_same(c, d):
    block_n[c-1] += 1
    block_n[d-1] += 1
    
  
V=list(uf.grouper())
renketu=[0]*N

for n in range(1,N+1):
  for v in V:
    if n in v:
      renketu[n-1]=len(v)

for n in range(N):
  print(renketu[n]-len(retu[n])-block_n[n]-1, end=" ")

Submission status: Wrong Answer

Solution code:
from  collections import deque
N,M,K=list(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)]

user=[0 for i in range(N+1)]
graph_ab=[[] for i in range(N+1)]
graph_cd=[[] for i in range(N+1)]
visit_list=[[] for i in range(N+1)]
for i in range(M):
    a,b=AB[i]
    graph_ab[a].append(b)
    graph_ab[b].append(a)
for i in range(K):
    c,d=CD[i]
    graph_cd[c].append(d)
    graph_cd[d].append(c)

for j in range(1,N+1):
    stack=deque([j])
    visited=[-1 for i in range(N+1)]
    visited[j]=0
    while stack:
        x=stack.popleft()
        for i in graph_ab[x]:
            if visited[i]<0:
                visited[i]=1
                stack.append(i)
    visit_list[j]=visited
for i in range(1,N+1):
    user[i]=visit_list[i].count(1)-len(graph_ab[i])
for i,value in enumerate(graph_cd):
    for j in value:
        if visit_list[i][j]==1:
            user[j]-=1
#     for i in range(j,N+1):
#         if visited[i]==1 and (i not in graph_ab[j]) and (i not in graph_cd[j]):
#             user[j]+=1
#             user[i]+=1
# del user[0]
print(*user)

Submission status: Wrong Answer

Solution code:
n,m,k = map(int,input().split())
A = [0]*m
B = [0]*m
C = [0]*k
D = [0]*k

relation = [[None for _ in range(n)] for _ in range(n)]
possibility = [[None for _ in range(n)] for _ in range(n)]

for i in range(m):
    A[i],B[i] = map(int,input().split())
    A[i] -= 1
    B[i] -= 1
    relation[A[i]][B[i]] = True
    relation[B[i]][A[i]] = True
    
for i in range(k):
    C[i],D[i] = map(int,input().split())
    C[i] -= 1
    D[i] -= 1
    relation[C[i]][D[i]] = False
    relation[D[i]][C[i]] = False

for i in range(n):
    relation[i][i] = False
    for j in range(n):
        if relation[i][j] == None:
            possibility[i][j] = relation[i][j]
        else:
            possibility[i][j] = False

def dfs(p,i,passed):
    passed[p] = True
    for j in range(n):
        if relation[p][j]==True and passed[j] == False:
            if j==i:
                possibility[p][i]=True
            else:
                p = j
                dfs(p,i,passed)
    
for p in range(n):
    for i in range(n):
        #目的の人
        if p != i and relation[p][i] == None:
            #経由の友達
            passed = [False for _ in range(n)]
            dfs(p,i,passed)

ans = [0]*n
for i in range(n):
    ans[i] = str(possibility[i].count(True))

print(" ".join(ans))

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [-1]*n
        
    def find(self, x):
        if self.par[x] < 0:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return 0
        if self.par[x] > self.par[y]:
            x, y = y, x
        self.par[x] = self.par[y] + self.par[x]
        self.par[y] = x

    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return self.par[self.find(x)]
    
    

n, m, k = map(int, input().split())
U = UnionFind(n)
fl = [0] * n
bl = [0] * n

for _ in range(m):
    a, b = map(int, input().split())
    U.union(a - 1, b - 1)
    fl[a - 1] += 1
    fl[b - 1] += 1

for _ in range(k):
    c, d = map(int, input().split())
    bl[c - 1] += 1
    bl[d - 1] += 1

ans_list = []
for i in range(n):
    ans = -U.size(i) - fl[i] - bl[i] - 1
    ans_list.append(ans)
print(*ans_list)

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)]  #数字、複数行複数列

left = []
right = []
import itertools
for i, j in itertools.combinations(range(1,N+1), 2):
    left.append(i)
    right.append(j)

#print(left)
#print(right)

bad = 0
for i in range(len(left)):
    a = left[i-bad]
    b = right[i-bad]
    if [a,b] in AB or [a,b] in CD :
        left.remove(left[i - bad])
        right.remove(right[i - bad])
        bad += 1
    elif [b, a] in AB or [b, a] in CD:
        left.remove(left[i - bad])
        right.remove(right[i - bad])
        bad += 1

ans = [0] * N
for i in range(1, N + 1):
    if i in left or i in right:
        ans[i - 1] += left.count(i)
        ans[i - 1] += right.count(i)

for i in ans:
    print(i, end=" ")  #ひとスペース間隔

Submission status: Wrong Answer

Solution code:
n,m,k = map(int,input().split())
ab = [[] for _ in range(n)]
sa = [1]*n
for _ in range(m):
    a, b= (int(x) for x in input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
    sa[a-1] += 1
    sa[b-1] += 1

bl = []
for _ in range(k):
    a, b= (int(x) for x in input().split())
    bl.append([a-1,b-1])

ans = [0]*n

for i in range(n):
    if ans[i] != 0:
        continue
    count = 1
    check = [-1]*n
    check[i] = 1
    stack=[i]
    while len(stack):
        v = stack.pop(0)
        for j in ab[v]:
            if check[j] == -1:
                count += 1
                check[j] = 1
                stack.append(j)
    for k in range(n):
        if check[k] == 1:
            ans[k] = count

for a, b in bl:
    if ans[a] == ans[b]:
        sa[a] += 1
        sa[b] += 1

for i in range(n):
    ans[i] -= sa[i]

print(*ans)

Submission status: Wrong Answer

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

N, M, K = map(int, input().split())
friend = [deque() for _ in range(N)]
status = [-1]*N
numList = [0]*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)
    ans[a-1] -= 1
    ans[b-1] -= 1

def DFS(graph, v, num):
    cnt = 0
    stack = [v]
    status[v] = num
    while stack:
        v = stack[-1]
        if graph[v]:
            w = graph[v].popleft()
            if status[w] == -1:
                status[w] = num
                cnt += 1
                stack.append(w) 
        else:
            stack.pop() 
    numList[num] = cnt

cnt = 0
for i in range(N):
    if status[i] == -1:
        DFS(friend, i, cnt)
        cnt += 1

for i in range(N):
    ans[i] = numList[status[i]]

for i in range(K):
    a, b = map(int, input().split())
    if status[a-1] == status[b-1]:
        ans[a-1] -= 1
        ans[b-1] -= 1

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

Submission status: Wrong Answer

Solution code:
# D - Friend Suggestions

from queue import Queue

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

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

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

Q = Queue()
cnt = [0] * N
for i in range(N):
    visited = [False] * N
    Q.put(friends[i])
    visited[i] = True
    while not Q.empty():
        q = Q.get()
        if (q[0] != i and
                q[0] not in friends[i][1] and
                q[0] not in blocks[i][1]):
            cnt[i] += 1
        for j in q[1]:
            if not visited[j]:
                visited[j] = True
                Q.put(friends[j])

print(cnt)

Submission status: Wrong Answer

Solution code:
n,m,k = list(map(int,input().split()))
ans_l =[0 for _ in range(n)] #答えを格納
friend = [[] for _ in range(n)]
friend_line =[i for i in range(n)]
for _ in range(m):
    a,b= list(map(int,input().split()))
    if not a-1 in friend[b-1]:
        friend[a-1].append(b-1)
        friend[b-1].append(a-1)

num = 0
while(num < n):
    #print(num)
    for x in friend[num]:
        friend_line[x]=friend_line[num]#グループナンバー
    num+=1
    #print(frend_line)

for _ in range(k):
    a,b= list(map(int,input().split()))
    if not a-1 in friend[b-1]:
        friend[a-1].append(b-1)
        friend[b-1].append(a-1)

#print(friend)
#print(friend_line)

for i in range(n):
    print(friend_line.count(friend_line[i])-1-len(friend[i]),end=" ")

Submission status: Wrong Answer

Solution code:
n,m,k = list(map(int,input().split()))
ans_l =[0 for _ in range(n)] #答えを格納
friend = [[] for _ in range(n)]
friend_line =[i for i in range(n)]
for _ in range(m):
    a,b= list(map(int,input().split()))
    if not a-1 in friend[b-1]:
        friend[a-1].append(b-1)
        friend[b-1].append(a-1)

num = 0
while(num < n):
    #print(num)
    for x in friend[num]:
        friend_line[x]=friend_line[num]#グループナンバー
    num+=1
    #print(frend_line)

for _ in range(k):
    a,b= list(map(int,input().split()))
    if not a-1 in friend[b-1]:
        friend[a-1].append(b-1)
        friend[b-1].append(a-1)

print(friend)
print(friend_line)

for i in range(n):
    print(friend_line.count(friend_line[i])-1-len(friend[i]),end=" ")

Submission status: Wrong Answer

Solution code:
n,m,k = list(map(int,input().split()))
ans_l =[0 for _ in range(n)] #答えを格納
frend = [[] for _ in range(n)]
group = [[] for _ in range(n)]
frend_line =[i for i in range(n)]
for _ in range(m):
    a,b= list(map(int,input().split()))
    frend[a-1].append(b-1)
    frend[b-1].append(a-1)
for _ in range(k):
    a,b= list(map(int,input().split()))
    group[a-1].append(b-1)
    group[b-1].append(a-1)
#print(frend)
num = 0
while(num < n):
    #print(num)
    for x in frend[num]:
        frend_line[x]=frend_line[num]#グループナンバー
    num+=1
    #print(frend_line)

#print(frend_line)
for i in range(n):
    for j in range(i+1,n):
        if not j in frend[i] and not j in group[i] and frend_line[i]==frend_line[j]:
            ans_l[i]+=1
            ans_l[j]+=1

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

Submission status: Wrong Answer

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

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 solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):
    A = [a-1 for a in A]
    B = [b - 1 for b in B]
    C = [c - 1 for c in C]
    D = [d - 1 for d in D]
    uf = UnionFind(N)
    block = collections.defaultdict(set)
    follow = collections.defaultdict(set)
    for a, b in zip(A, B):
        uf.union(a, b)
        follow[a].add(b)
        follow[b].add(a)
    for c, d in zip(C, D):
        block[d].add(c)
        block[c].add(d)
    result = []
    for i in range(N):
        result.append(len(set(uf.members(i)) - block[i] - follow[i]) -1)
    result = [str(x) for x in result]
    print(' '.join(result))
    return

Submission status: Wrong Answer

Solution code:
#Union Find
#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

N,M,K = map(int,input().split())
#初期化
#根なら-size,子なら親の頂点
par = [-1]*(N+1)

friends = [[]for i in range(0,N+1,1)]
block = [[]for i in range(0,N+1,1)]
for i in range(0,M,1):
    a,b = map(int,input().split())
    friends[a].append(b)
    friends[b].append(a)
    unite(a,b)
for i in range(0,K,1):
    a,b=map(int,input().split())
    block[a].append(b)
    block[b].append(a)

countmem = [0]*N
for i in range(1,N+1,1):
    count = size(i)-1
    mem = []
    ma = mem.append
    for j in range(0,len(friends[i]),1):
        if same(i,friends[i][j]):
            count -=1
            ma(i)
    for j in range(0,len(block[i]),1):
        if same(i,block[i][j]) and not(j in mem):
            count -=1
    countmem[i-1]=count

print(*countmem)

Submission status: Wrong Answer

Solution code:
n, m, k = map(int, input().split())
a = [0]*m
c = [0]*k

union = []
sets = []
for i in range(n+1):
    union.append(i)
    sets.append({i})

def root(n):
    global union
    if union[n] == n:
        return n
    res = union[union[n]]
    union[n] = res
    return res

def isSameRoots(n, m):
    nRoot = root(n)
    mRoot = root(m)
    return nRoot == mRoot

def unit(n, m):
    global union
    global sizeU
    global sets
    nRoot = root(n)
    mRoot = root(m)
    sets[nRoot] = sets[nRoot] | sets[mRoot]
    union[mRoot] = root(nRoot)

friends = [0]*(n+1)
for i in range(m):
    inA, inB = map(int, input().split())
    friends[inA] += 1
    friends[inB] += 1
    if not isSameRoots(inA, inB):
        unit(inA, inB)

for i in range(k):
    inA, inB = map(int, input().split())
    if isSameRoots(inA, inB):
        friends[inA] += 1
        friends[inB] += 1

for i in range(1, n+1):
    print(len(sets[root(i)]) - friends[i] - 1)

Submission status: Wrong Answer

Solution code:
n, m, k = map(int, input().split())
a = [0]*m
c = [0]*k

union = []
sets = []
for i in range(n+1):
    union.append(i)
    sets.append({i})

def root(n):
    global union
    if union[n] == n:
        return n
    res = union[union[n]]
    union[n] = res
    return res

def isSameRoots(n, m):
    nRoot = root(n)
    mRoot = root(m)
    return nRoot == mRoot

def unit(n, m):
    global union
    global sizeU
    global sets
    nRoot = root(n)
    mRoot = root(m)
    sets[nRoot] = sets[nRoot] | sets[mRoot]
    union[mRoot] = root(nRoot)

friends = [0]*(n+1)
for i in range(m):
    inA, inB = map(int, input().split())
    friends[inA] += 1
    friends[inB] += 1
    if not isSameRoots(inA, inB):
        unit(inA, inB)

for i in range(k):
    inA, inB = map(int, input().split())
    if {inB} <= sets[root(inA)]:
        friends[inA] += 1
    if {inA} <= sets[root(inB)]:
        friends[inB] += 1

for i in range(1, n+1):
    print(len(sets[root(i)]) - friends[i] - 1)

Submission status: Wrong Answer

Solution code:
n, m, k = map(int, input().split())
a = [0]*m
c = [0]*k

union = []
sizeU = [1]*(n+1)
for i in range(n+1):
    union.append(i)

def root(n):
    global union
    if union[n] == n:
        return n
    res = union[union[n]]
    union[n] = res
    return res

def isSameRoots(n, m):
    nRoot = root(n)
    mRoot = root(m)
    return nRoot == mRoot

def unit(n, m):
    global union
    global sizeU
    nRoot = root(n)
    mRoot = root(m)
    sizeU[nRoot] += size(mRoot)
    union[mRoot] = root(nRoot)

def size(n):
    return sizeU[root(n)]

for i in range(m):
    inA, inB = map(int, input().split())
    if not isSameRoots(inA, inB):
        unit(inA, inB)

for i in range(1, n+1):
    print(size(i))

Submission status: Wrong Answer

Solution code:
import numpy as np

n, f, b = map(int, input().split())
F = [list(map(int, input().split())) for i in range(f)]
B = [list(map(int, input().split())) for i in range(b)]

R=[]

for i in range(1,n+1):
    R.append(set([i]))

f_sets=[]

for friend in F:
    R[friend[0]-1].add(friend[1])
    R[friend[1]-1].add(friend[0])

    set0 = -1
    set1 = -1

    for i, f_set in enumerate(f_sets):
        if friend[0] in f_set:
            set0 = i
        if friend[1] in f_set:
            set1 = i

    if set0==-1 and set1==-1:
        f_sets.append(set(friend))

    if set0==-1 and set1!=-1:
        f_sets[set1].add(friend[0])

    if set0!=-1 and set1==-1:
        f_sets[set0].add(friend[1])

    if set0!=-1 and set1!=-1 and set0!=set1:
        f_sets[set0]=f_sets[set0]|f_sets[set1]
        f_sets.pop(set1)

for block in B:
    R[block[0]-1].add(block[1])
    R[block[1]-1].add(block[0])

ans=[]
for i in range(1,n+1):
    for f_set in f_sets:
        if i in f_set:
             ans.append(len(f_set-R[i-1]))
             break

print(' '.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
from collections import defaultdict
sys.setrecursionlimit(10**7)
def run():
    N,M,K = map(int,sysread().split())
    to = [[] for _ in range(N+1)]
    n_to = [0 for _ in range(N + 1)]
    for i in range(1,M+1):
        a,b = map(int, sysread().split())
        #a,b = AB[i]
        to[a].append(b)
        n_to[a] += 1
        to[b].append(a)
        n_to[b] += 1

    stack = defaultdict(lambda:0)
    visited = [False] * (N+1)
    belong = [None] * (N+1)


    def dfs(n):
        _stack = [n]
        visited[n] = True
        while _stack:
            node = _stack.pop()
            stack[n] += 1
            belong[node] = n
            for next in to[node]:
                if not visited[next]:
                    _stack.append(next)
                    visited[next] = True
        return None


    for i in range(1,N+1):
            dfs(i)

    block = [0 for _ in range(N+1)]
    for i in range(1, K+1):
        c,d = map(int, sysread().split())
        #c, d = CD[i]
        if belong[c] == belong[d]:
            block[c] += 1
            block[d] += 1

    candidates = [0] * (N+1)

    for tree in stack.keys():
        for k in range(1,N+1):
            tr = belong[k]
            candidates[k] = stack[tr] - 1 - n_to[k] - block[k]

    print(' '.join(map(str, candidates[1:])))

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

friend = defaultdict(set)
block  = defaultdict(set)

class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.siz = [1 for i in range(n)]

  def merge(self, a, b):
    a,b = self.root(a), self.root(b)
    if a == b: return False
    if self.siz[a] < self.siz[b]: a, b = b, a
    self.siz[a] += self.siz[b]
    self.par[b] = a
    return True

  def root(self, a):
    while self.par[a] != a:
      a = self.par[a] = self.par[self.par[a]]
    return a

  def issame(self, a, b):
    return self.root(a) == self.root(b)

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

uf = UnionFind(n)
f = lambda x: int(x) - 1
for i in range(m):
  a, b = map(f, input().split())
  friend[a] |= {b}
  friend[b] |= {a}
  uf.merge(a, b)
for i in range(k):
  a, b = map(f, input().split())
  block[a] |= {b}
  block[b] |= {a}

rui = defaultdict(set)
for i in range(n):
  rui[uf.root(i)] |= {i}
drui = {}
for k,v in rui.items():
  for i in v:
    drui[i] = v

count = lambda node: str(len(drui[node] - {node} - block[node] - friend[node]))
res = [count(i) for i in range(n)]

print(' '.join(res))

Submission status: Wrong Answer

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

N, M, K = map(int, input().split())
friends_table = [[] for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    friends_table[a-1] += [b-1]
    friends_table[b-1] += [a-1]

group_list = [i for i in range(N)]
friends_candidate = [[] for i in range(N)]

for i in range(N):
    friend = [i]
    # すでにDFS済み
    if i != group_list[i]:
        continue
    next_stack = friends_table[i][:]
    while next_stack:
        u = next_stack.pop(-1)
        for v in friends_table[u]:
            # 訪問済み
            if i == group_list[v]:
                continue
            friend += [v]
            group_list[v] = i
            next_stack += [v]
    for f in friend:
        friends_candidate[f] = friend

blocks_table = [[] for i in range(N)]
for _ in range(K):
    a, b = map(int, input().split())
    if group_list[a-1] == group_list[b-1]:
        blocks_table[a-1] += [b-1]
        blocks_table[b-1] += [a-1]

for i in range(N):
    print(len(friends_candidate[i]) - len(friends_table[i]) - len(blocks_table[i])-1)

Submission status: Wrong Answer

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

N, M, K = map(int, input().split())
friends_table = [[] for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    friends_table[a-1] += [b-1]
    friends_table[b-1] += [a-1]

blocks_table = [[] for i in range(N)]
for _ in range(K):
    a, b = map(int, input().split())
    blocks_table[a-1] += [b-1]
    blocks_table[b-1] += [a-1]

group_list = [i for i in range(N)]
friends_candidate = [[] for i in range(N)]

for i in range(N):
    friend = [i]
    # すでにDFS済み
    if i != group_list[i]:
        continue
    next_stack = friends_table[i][:]
    while next_stack:
        u = next_stack.pop(-1)
        for v in friends_table[u]:
            # 訪問済み
            if i == group_list[v]:
                continue
            friend += [v]
            group_list[v] = i
            next_stack += [v]
    for f in friend:
        friends_candidate[f] = friend

for i in range(N):
    print(len(friends_candidate[i]) - len(friends_table[i]) - len(blocks_table[i])-1)

Submission status: Wrong Answer

Solution code:
import time



def solve():
    print("a")
    us = [[i] for i in range(0,n+1)]
    for i in range(1, n + 1):
        for fr in fs[i]:
            if not us[i] is us[fr]:
                if len(us[i])>len(us[fr]):
                    us[i].extend(us[fr])
                    for aa in us[fr]:
                        us[aa] = us[i]
                else:
                    us[fr].extend(us[i])
                    for aa in us[i]:
                        us[aa] = us[fr]
    for i in range(1, n + 1):
        frens = len(us[i]) - 1 - len(fs[i])
        for blo in bs[i]:
            if blo in us[i]:
                frens -= 1
        print(frens, end=" ")
    print()
    return


n, m, k = [int(s) for s in input().split(" ")]

fs = [[] for i in range(n + 1)]
bs = [[] for i in range(n + 1)]

for i in range(m):
    a, b = [int(s) for s in input().split(" ")]
    fs[a].append(b)
    fs[b].append(a)
for i in range(k):
    c, d = [int(s) for s in input().split(" ")]
    bs[c].append(d)
    bs[d].append(c)
solve()

Submission status: Wrong Answer

Solution code:
# UnionFind: https://note.nkmk.me/python-union-find/
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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        
    def is_same(self, x, y):
        return self.parents[x] == self.parents[y]
    
    def size(self, x):
        return -self.parents[self.find(x)]
    
candidate = [-1] * n
f_ship = UnionFind(n)
for _ in range(m):
    a, b = map(int, input().split())
    candidate[a - 1] -= 1
    candidate[b - 1] -= 1
    f_ship.unite(a - 1, b - 1)
for _ in range(k):
    c, d = map(int, input().split())
    if f_ship.is_same(c - 1, d - 1):
        candidate[c - 1] -= 1
        candidate[d - 1] -= 1
for i in range(n):
    candidate[i] += f_ship.size(i)
print(*candidate)