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:
N, M, K = map(int, input().split())
F = [[] for _ in range(N)]
B = [[] for _ in range(N)]

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

print(F)

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


class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根(最初は全て根)
        self.par = [i for i in range(n)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * n
        # 人間の数
        self.size = [1] * n

    # 検索
    def find(self, x):
        # 根ならその番号を返す
        if self.par[x] == x:
            return x
        # 根でないなら、親の要素で再検索
        else:
            # 走査していく過程で親を書き換える(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
        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


UF = UnionFind(N)
for iam in range(N):
    for friend in F[iam]: 
        UF.union(iam, friend) # 自分と自分の友達を併合

ans = [UF.size[UF.find(iam)] - 1 for iam in range(N)] # 同じ集合に属する人の数

for iam in range(N):
    ans[iam] -= len(F[iam]) # すでに友達関係にある人達を引く

for iam in range(N):
    for block in B[iam]:
        if UF.same(iam, block): # ブロック関係にあったら引く
            ans[iam] -= 1

print(*ans, sep=' ')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(200100)
def abc157_d():
    N, M, K = map(int, input().split())
    fr = [set() for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        fr[a].add(b)
        fr[b].add(a)
    bl = [set() for _ in range(N)]
    for _ in range(K):
        c, d = map(int, input().split())
        c, d = c-1, d-1
        bl[c].add(d)
        bl[d].add(c)

    def dfs(nd, lb):
        nonlocal label, gr
        label[nd] = lb
        gr[lb].add(nd)
        for ch in fr[nd]:
            if label[ch] != -1: continue
            dfs(ch, lb)

    label = [-1] * N
    lb = 0
    gr = []
    for i in range(N):
        if label[i] != -1: continue
        gr.append(set())
        dfs(i, lb)
        lb += 1

    return

    ans = [0] * N
    for i in range(N):
        cand = gr[label[i]] - fr[i] - bl[i]
        ans[i] = len(cand) - 1
    print(*ans, sep=' ')

abc157_d()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n, m, k = map(int, input().split())
friend = defaultdict(set)
block = defaultdict(set)
for i in range(m):
    a, b = map(int, input().split())
    friend[a].add(b)
    friend[b].add(a)
for i in range(k):
    a, b = map(int, input().split())
    block[a].add(b)
    block[b].add(a)
res = [0] * n
for i in range(1, n + 1):
    if len(friend[i]) == n - 1 or len(friend[i]) == 0:
        continue
    queue = list(friend[i])
    while queue:
        j = queue.pop(0)
        for k in friend[j]:
            if k != i and k not in friend[i] and k not in block[i]:
                res[i-1] += 1
                friend[i].add(k)
                queue.append(k)
                if i not in friend[k]:
                    res[k-1] += 1
                    friend[k].add(i)
for i in range(n):
    print(res[i], end=" ")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n, m, k = map(int, input().split())
friend = defaultdict(list)
block = defaultdict(list)
for i in range(m):
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a
    friend[a].append(b)
for i in range(k):
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a
    block[a].append(b)
res = [0] * n
for i in range(1, n + 1):
    if len(friend[i]) == n - 1 or len(friend[i]) == 0:
        continue
    for j in friend[i]:
        for k in friend[j]:
            if k not in friend[i] and k not in block[i]:
                res[i - 1] += 1
                res[k-1] += 1
for i in range(n):
    print(res[i],end = " ")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n, m, k = map(int, input().split())
friend = defaultdict(list)
block = defaultdict(list)
for i in range(m):
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a
    friend[a].append(b)
for i in range(k):
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a
    block[a].append(b)
res = [0] * n
for i in range(1, n + 1):
    if len(friend[i]) == n - 1 or len(friend[i]) == 0:
        continue
    for j in friend[i]:
        for k in friend[k]:
            if k not in friend[i] and k not in block[i]:
                res[i - 1] += 1
for i in range(n):
    print(res[i], sep = " ")

Submission status: Wrong Answer

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)

    answers = []
    networks = {}
    net_leaders = [-1] * n
    visited = set()
    for person in range(n):
        if person in visited:
            continue
        networks[person] = set()
        stack = deque([person])
        while stack:
            new = stack.pop()
            visited.add(new)
            net_leaders[new] = person
            networks[person].add(new)
            for adj in friends[new]:
                if adj in visited:
                    continue
                stack.append(adj)
    for pp in range(n):
        net = networks[net_leaders[pp]]
        ans = len(net) - len(friends[person]) - 1
        answers.append(ans)

    print(*answers)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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)

    answers = []
    networks = {}
    net_leaders = [-1] * n
    visited = set()
    for person in range(n):
        if person in visited:
            continue
        networks[person] = set()
        stack = deque([person])
        while stack:
            new = stack.pop()
            visited.add(new)
            net_leaders[new] = person
            networks[person].add(new)
            for adj in friends[new]:
                if adj in visited:
                    continue
                stack.append(adj)
    for pp in range(n):
        net = networks[net_leaders[pp]]
        ans = len(net) - len(friends[person]) - len(net & blocks[person]) - 1
        answers.append(ans)

    print(*answers)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def BFS(x):
  cnt=1
  v=deque([x])
  k=0
  zu[x]=k
  lis=[x]
  
  while len(v)>0:
    a=v.popleft()
    for i in fr[a]:
      if zu[i]==-1:
        zu[i]=zu[a]+1
        v.append(i)
        cnt += 1
        lis.append(i)
          
  return lis

##############################

from collections import deque
N,M,K=map(int,input().split())
A=[0]*M
B=[0]*M
C=[0]*K
D=[0]*K
fr=[ [] for _ in range(N)]
bl=[ set() for _ in range(N)]
zu=[ -1 for _ in range(N)] #訪問済みリスト

for i in range(M):
  A[i],B[i]= map(int,input().split())
  fr[A[i]-1].append(B[i]-1)
  fr[B[i]-1].append(A[i]-1)
for k in range(K):
  C[k],D[k]= map(int,input().split())
  bl[C[k]-1].add(D[k]-1)
  bl[D[k]-1].add(C[k]-1)
    
size=[0]*N
pena=[0]*N
for i in range(N):
  if zu[i]==-1:
    kumi=BFS(i) #リスト
    
#    for k in range(len(kumi)):
#      size[kumi[k]]=len(kumi)
#      for l in range(len(kumi)):
#        if l==k:
#          pass
#        else:
#          if (kumi[l] in bl[kumi[k]]) or (kumi[l] in fr[kumi[k]]):
#            #print(kumi[k],kumi[l],bl[kumi[k]],fr[kumi[k]])
#            pena[kumi[k]] += 1
#print(size)
#print(pena)
#ans=[]
#for i in range(N):
#  ans.append(size[i]-pena[i]-1)
#print(*ans)

Submission status: Wrong Answer

Solution code:
def BFS(x):
  cnt=1
  v=deque([x])
  k=0
  zu[x]=k
  lis=[x]
  
  while len(v)>0:
    a=v.popleft()
    for i in fr[a]:
      if zu[i]==-1:
        zu[i]=zu[a]+1
        v.append(i)
        cnt += 1
        lis.append(i)
          
  return lis

##############################

from collections import deque
N,M,K=map(int,input().split())
A=[0]*M
B=[0]*M
C=[0]*K
D=[0]*K
fr=[ [] for _ in range(N)]
bl=[ set() for _ in range(N)]
zu=[ -1 for _ in range(N)] #訪問済みリスト

for i in range(M):
  A[i],B[i]= map(int,input().split())
  fr[A[i]-1].append(B[i]-1)
  fr[B[i]-1].append(A[i]-1)
for k in range(K):
  C[k],D[k]= map(int,input().split())
  bl[C[k]-1].add(D[k]-1)
  bl[D[k]-1].add(C[k]-1)
    
size=[0]*N
pena=[0]*N

kumi=BFS(0)

Submission status: Wrong Answer

Solution code:
def BFS(x):
  cnt=0
  v=deque([x])
  zu=[ -1 for _ in range(N)] #訪問済みリスト
  k=0
  zu[x]=k
  
  while len(v)>0:
    a=v.popleft()
    for i in fr[a]:
      if zu[i]==-1:
        zu[i]=zu[a]+1
        v.append(i)
        #if zu[i]>1 and (i not in bl[x]):
        cnt +=1            
  return cnt

##############################

from collections import deque
N,M,K=map(int,input().split())
A=[0]*M
B=[0]*M
C=[0]*K
D=[0]*K
fr=[ [] for _ in range(N)]
bl=[ set() for _ in range(N)]

for i in range(M):
  A[i],B[i]= map(int,input().split())
  fr[A[i]-1].append(B[i]-1)
  fr[B[i]-1].append(A[i]-1)
for k in range(K):
  C[k],D[k]= map(int,input().split())
  bl[C[k]-1].add(D[k]-1)
  bl[D[k]-1].add(C[k]-1)

ans=[]  
for i in range(N):
  ans.append(BFS(i))
print(*ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

class UnionFind():
    def __init__(self, n):      #初期化
        self.n = n
        # 親
        self.parents = [i for i in range(n)]
        # 木の深さ
        self.ranks = [0] * n
        # グループの要素数
        self.sizes = [1] * n

    def find(self, x):          #親を出力
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

        if x == y:
            return

        if self.ranks[x] < self.ranks[y]:
            self.parents[x] = y
            self.sizes[y] += self.sizes[x]
        else:
            self.parents[y] = x
            self.sizes[x] += self.sizes[y]
            if self.ranks[x]==self.ranks[y]:
                self.ranks[x] += 1

    def same(self, x, y):       #xとyが同じグループかどうか
        return self.find(x) == self.find(y)

    def members(self, x):       #xと同じグループの要素
        root = self.find(x)
        return {i for i in range(self.n) if self.find(i) == root}

    def size(self, x):          #グループの要素数
        root = self.find(x)
        return self.sizes[root]

    def roots(self):            #親の要素一覧
        return {i for i, x in enumerate(self.parents) if i == x}

    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 = map(int, input().split())
    uf = UnionFind(N)
    dic = {i:set([i]) for i in range(N)}

    for i in range(M):
        a,b = map(int,input().split())
        uf.unite(a-1, b-1)
        dic[a-1].add(b-1)
        dic[b-1].add(a-1)

    for j in range(K):
        a,b = map(int,input().split())
        dic[a-1].add(b-1)
        dic[b-1].add(a-1)

    ret = [None]*N
    for i in range(N):
        cnt = 0
        print(uf.members(i))
        for x in uf.members(i):
            cnt += not x in dic[i]
        ret[i]=cnt
    print(" ".join(map(str,ret)))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

for _ in range(K):
    A, B = map(int, input().split())
    NG[A - 1].add(B - 1)
    NG[B - 1].add(A - 1)
T = [-1] * N
que = deque()
que.append(0)
c = 1
while que:
    v = que.popleft()
    for e in G[v]:
        if T[e] == -1:
            T[e] = c
            que.append(e)
    c + 1
CNT = [0] * N
for i in range(N):
    CNT[i] = T.count(T[i])

for i in range(N):
    CNT[i] -= 1
for i in range(N):
    for j in NG[i]:
        if T[i]==T[j]:
            CNT[i]-=1
print(*CNT)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

for _ in range(K):
    A, B = map(int, input().split())
    NG[A - 1].append(B - 1)
    NG[B - 1].append(A - 1)
T = [-1] * N
que = deque()
que.append(0)
c = 1
while que:
    v = que.popleft()
    for e in G[v]:
        if T[e] == -1:
            T[e] = c
            que.append(e)
    c + 1
CNT = [0] * N
for i in range(N):
    CNT[i] = T.count(T[i])

for i in range(N):
    CNT[i] -= 1
for i in range(N):
    for j in NG[i]:
        if T[i] == T[j]:
            CNT[i] -= 1
print(*CNT)

Submission status: Wrong Answer

Solution code:
from collections import deque

n,m,k=map(int,input().split())
fre=[[]for _ in range(n)]
blo=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    fre[a-1].append(b-1)
    fre[b-1].append(a-1)
for i in range(k):
    c,d=map(int,input().split())
    blo[c-1].append(d-1)
    blo[d-1].append(c-1)

cnt=[0]*n
l=deque()
x=1
dic={}
for i in range(n):
    if cnt[i]==0:
        l.append(i)
    while l:
        now=l.popleft()
        for to in fre[now]:
            if cnt[to]==0:
                cnt[to]=x
                if x in dic:
                    dic[x]+=1
                else:
                    dic[x]=1
                l.append(to)
    x+=1

for i in range(n):
    if dic=={}:
        print(0)
    k=len(fre[i])
    for b in blo[i]:
        if cnt[b]==cnt[i]:
            k+=1
    if cnt[i] in dic:
        print(dic[cnt[i]]-k-1)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
from collections import deque

n,m,k=map(int,input().split())
fre=[[]for _ in range(n)]
blo=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    fre[a-1].append(b-1)
    fre[b-1].append(a-1)
for i in range(k):
    c,d=map(int,input().split())
    blo[c-1].append(d-1)
    blo[d-1].append(c-1)

cnt=[0]*n
l=deque()
x=1
dic={}
for i in range(n):
    if cnt[i]==0:
        l.append(i)
    while l:
        now=l.popleft()
        for to in fre[now]:
            if cnt[to]==0:
                cnt[to]=x
                if x in dic:
                    dic[x]+=1
                else:
                    dic[x]=1
                l.append(to)
    x+=1

for i in range(n):
    if dic=={}:
        print(0)
    k=len(fre[i])
    for b in blo[i]:
        if cnt[b]==cnt[i]:
            k+=1
    if cnt[i] in dic:
        print(dic[cnt[i]]-k-1)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
n, m, k = map(int, input().split())
friends = defaultdict(list)
block = defaultdict(list)
for _ in range(m):
    a, b = map(int, input().split())
    friends[a].append(b)
    friends[b].append(a)
for _ in range(k):
    c, d = map(int, input().split())
    block[c].append(d)
    block[d].append(c)
#print(friends)
#print(block)

roopname = []
roop = defaultdict(list)
seen = [-1]*n


for i in range(n):
    if not seen[i]==-1:
        continue
    roopname.append(i+1)
    queue = deque(friends[i+1])
    while queue:
        p = queue.popleft()
        if  not seen[p-1]==-1:continue
        seen[p-1] = i+1
        roop[i+1].append(p)
        for j in friends[p]:
            if seen[j-1]==-1:
                queue.append(j)
#print(roopname)
#print(roop)
#print(seen)
ans = []
for i in range(n):
    fsum = 0
    for j in friends[i+1]:
        if j in roop[seen[i]]:
            fsum += 1
            
    bsum = 0
    for j in block[i+1]:
        if j in roop[seen[i]]:
            bsum += 1
    
    ans.append(len(roop[seen[i]])-bsum-fsum-1)

L=[str(a) for a in ans]
L=" ".join(L)
print(L)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
n, m, k = map(int, input().split())
friends = defaultdict(list)
block = defaultdict(list)
for _ in range(m):
    a, b = map(int, input().split())
    friends[a].append(b)
    friends[b].append(a)
for _ in range(k):
    c, d = map(int, input().split())
    block[c].append(d)
    block[d].append(c)
print(friends)
print(block)
ans =[]
for i in range(n):
    ans.append(n-len(friends[i+1])-len(block[i+1])-1)
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
sys.setrecursionlimit(2000)
N,M,K=list(map(int,input().split()))
friend_list=[set() for _ in range(N+1)]
block_list=[set() for _ in range(N+1)]
def friend_tansaku(i,j):
    color.add(j)
    for friend in friend_list[j]:
        if friend not in color:
            if friend not in block_list[i] and friend not in candidate and friend not in friend_list[i]:
                candidate.add(friend)
                count[0]+=1
            # friend_tansaku(i,friend)




for _ in range(M):
   a,b= list(map(int, input().split()))
   friend_list[a].add(b)
   friend_list[b].add(a)
for _ in range(K):
    a, b = list(map(int, input().split()))
    block_list[a].add(b)
    block_list[b].add(a)
for i in range(1,N+1):
    count=[0]
    color =set()
    candidate=set()
    friend_tansaku(i,i)
    if i==N:print(count[0])
    else:print(count[0],end=" ")

Submission status: Wrong Answer

Solution code:
from sys import stdin
N,M,K=list(map(int,input().split()))
friend_list=[set() for _ in range(N+1)]
block_list=[set() for _ in range(N+1)]
def friend_tansaku(i,j):
    color.add(j)
    for friend in friend_list[j]:
        if friend not in color:
            if friend not in block_list[i] and friend not in candidate and friend not in friend_list[i]:
                candidate.add(friend)
                count[0]+=1
            friend_tansaku(i,friend)




for _ in range(M):
   a,b= list(map(int, input().split()))
   friend_list[a].add(b)
   friend_list[b].add(a)
for _ in range(K):
    a, b = list(map(int, input().split()))
    block_list[a].add(b)
    block_list[b].add(a)
for i in range(1,N+1):
    count=[0]
    color =set()
    candidate=set()
    # friend_tansaku(i,i)
    if i==N:print(count[0])
    else:print(count[0],end=" ")

Submission status: Wrong Answer

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        self.parents = [-1] * n
    def find(self, x):
        if 0 > self.parents[x]:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # 要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    # 全ての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if 0 > x]
    # グループの数を返す
    def group_count(self):
        return len(self.roots())
    # 辞書{根の要素: [そのグループに含まれる要素のリスト], ...}を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    # print()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M, K = MAP()
friends = defaultdict(list)
tree = UnionFind(N)
for _ in range(M):
	A, B = MAP()
	tree.union(A-1, B-1)
	friends[A-1].append(B-1)
	friends[B-1].append(A-1)

blocks = defaultdict(list)
for _ in range(K):
	C, D = MAP()
	blocks[C-1].append(D-1)
	blocks[D-1].append(C-1)

for i in range(N):
	minus = 0
	for b in blocks[i]:
		if tree.same(i, b):
			minus += 1
	print(tree.size(i)-len(friends[i])-1-minus, end = "")
print()

"""
print("friends")
print(friends)

print("blocks")
print(blocks)

i = 1
print("i={}".format(i))
print("tree.size(i)={}".format(tree.size(i)))
print("tree.find(i))={}".format(tree.find(i)))
print("tree.members(i)={}".format(tree.members(i)))
print("tree.roots={}".format(tree.roots()))
print("tree.group_count={}".format(tree.group_count()))
print("tree.all_group_members={}".format(tree.all_group_members()))
"""

Submission status: Wrong Answer

Solution code:
# UnionFind木
class UnionFind:
    def __init__(self, n):
        # その節の根、その節を含む木の高さ、その節が根の時の木のノード数
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    # 根を検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            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
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    # 木のノード数を得る
    def getSize(self, x):
        return self.size[self.find(x)]

N,M,K = map(int, input().split())
# 広義の友達 - 直接の友達 - ブロック
# UnionFind木
uftree = UnionFind(N)
count = [0] * N
for i in range(M):
    A,B = map(lambda x:x-1, map(int, input().split()))
    uftree.union(A,B)
    count[A] += 1
    count[B] += 1
for i in range(K):
    C,D = map(lambda x:x-1, map(int, input().split()))
    if uftree.same_check(C,D):
        count[C] += 1
        count[D] += 1
ans = [0] * N
for i in range(N):
    print(uftree.getSize(i))
    print(count[i])
    ans[i] = uftree.getSize(i) - 1 - count[i] # 真ん中の-1は自分自身

print(*ans)

Submission status: Wrong Answer

Solution code:
def main():
    # UnionFind木
    class UnionFind:
        def __init__(self, n):
            # その節の根、その節を含む木の高さ、その節が根の時の木のノード数
            self.par = [i for i in range(n)]
            self.rank = [0] * n
            self.size = [1] * n

        # 根を検索
        def find(self, x):
            if self.par[x] == x:
                return x
            else:
                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
            if self.rank[x] < self.rank[y]:
                self.par[x] = y
                self.size[y] += self.size[x]
            else:
                self.par[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

        # 同じ集合に属するか判定
        def same_check(self, x, y):
            return self.find(x) == self.find(y)

        # 木のノード数を得る
        def getSize(self, x):
            return self.size[self.find(x)]

    N,M,K = map(int, input().split())
    # 広義の友達 - 直接の友達 - ブロック
    # UnionFind木
    uftree = UnionFind(N)
    count = [0] * N
    for i in range(M):
        A,B = map(lambda x:x-1, map(int, input().split()))
        uftree.union(A,B)
        count[A] += 1
        count[B] += 1
    for i in range(K):
        C,D = map(lambda x:x-1, map(int, input().split()))
        if uftree.same_check(C,D):
            count[C] += 1
            count[D] += 1
    ans = [0] * N
    for i in range(N):
        print(uftree.getSize(i))
        print(count[i])
        ans[i] = uftree.getSize(i) - 1 - count[i] # 真ん中の-1は自分自身
    print(*ans)

main()

Submission status: Wrong Answer

Solution code:
# UnionFind木
class UnionFind:
    def __init__(self, n):
        # その節の根、その節を含む木の高さ、その節が根の時の木のノード数
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    # 根を検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            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
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    # 木のノード数を得る
    def getSize(self, x):
        return self.size[self.find(x)]

def main():
    N,M,K = map(int, input().split())
    # 広義の友達 - 直接の友達 - ブロック
    # UnionFind木
    uftree = UnionFind(N)
    count = [0] * N
    for i in range(M):
        A,B = map(lambda x:x-1, map(int, input().split()))
        uftree.union(A,B)
        count[A] += 1
        count[B] += 1
    for i in range(K):
        C,D = map(lambda x:x-1, map(int, input().split()))
        if uftree.same_check(C,D):
            count[C] += 1
            count[D] += 1
    ans = [0] * N
    for i in range(N):
        print(uftree.getSize(i))
        print(count[i])
        ans[i] = uftree.getSize(i) - 1 - count[i] # 真ん中の-1は自分自身
    print(*ans)

main()

Submission status: Wrong Answer

Solution code:
# UnionFind木
class UnionFind:
    def __init__(self, n):
        # その節の根、その節を含む木の高さ、その節が根の時の木のノード数
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    # 根を検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            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
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    # 木のノード数を得る
    def getSize(self, x):
        return self.size[self.find(x)]

def main():
    N,M,K = map(int, input().split())
    # 広義の友達 - 直接の友達 - ブロック
    # UnionFind木
    uftree = UnionFind(N)
    count = [0] * N
    for i in range(M):
        A,B = map(lambda x:x-1, map(int, input().split()))
        uftree.union(A,B)
        count[A] += 1
        count[B] += 1
    for i in range(K):
        C,D = map(lambda x:x-1, map(int, input().split()))
        if uftree.same_check(C,D):
            count[C] += 1
            count[D] += 1
    ans = [""] * N
    for i in range(N):
        print(uftree.getSize(i))
        print(count[i])
        ans[i] = str(uftree.getSize(i) - 1 - count[i]) # 真ん中の-1は自分自身
    print(*ans, sep=" ")

main()