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:
# -*- coding: utf-8 -*-

N,M,K=[int(i) for i in input().rstrip().split()]
AB_list=[[int(j) for j in input().split()] for i in range(M)]
CD_list=[[int(j) for j in input().split()] for i in range(K)]
#-----

friend_dic={}  # dic{ int: set()}
block_dic={}   # dic{ int: set()}

for iA,iB in AB_list:
    friend_dic.setdefault(iA,set())
    friend_dic[iA].add(iB)
    friend_dic.setdefault(iB,set())
    friend_dic[iB].add(iA)

for iC,iD in CD_list:
    block_dic.setdefault(iC,set())
    block_dic[iC].add(iD)
    block_dic.setdefault(iD,set())
    block_dic[iD].add(iC)

ans=[]
for i in range(1,N+1):
    ex_set=set()
    if i in friend_dic:
        ex_set = ex_set | friend_dic.get(i)
    if i in block_dic:
        ex_set = ex_set | block_dic.get(i)
    
    ans += [N-1-len(ex_set)]
    
print(*ans)

Submission status: Wrong Answer

Solution code:
#!/bin/bash
""":"
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 \
   /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/g.inp"
exit $?
"""
import sys


def _ia(offset=0): return [int(x) + offset for x in sys.stdin.readline().strip().split()]


def main():
    n, m, k = _ia()
    ab = []
    g = [i for i in range(n)]
    for _ in range(m):
        i, j = _ia(-1)
        ab.append([i, j])
    #
    for _ in range(23):
        for abi in ab:
            i, j = abi
            g[i] = g[j] = min(g[i], g[j])
    for _ in range(k):
        ab.append(_ia(-1))

    ng = max(g) + 1
    dg = [0] * ng
    for gi in g: dg[gi] += 1
    #
    r = [0] * n
    for abi in ab:
        i, j = abi
        gi, gj = g[i], g[j]
        if gi == gj:
            r[i] += 1
            r[j] += 1
    return " ".join([str(dg[g[i]] - r[i] - 1) for i in range(n)])


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

Submission status: Wrong Answer

Solution code:
from collections import deque

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


friendship = {}
for i in range(m):
    a, b = list(map(int, input().split()))
    if a in friendship.keys():
        friendship[a].append(b)
    else:
        friendship[a] = [b]
        
    if b in friendship.keys():
        friendship[b].append(a)
    else:
        friendship[b] = [a]
        
block = {}
for j in range(k):
    c, d = list(map(int, input().split()))
    if c in block.keys():
        block[c].append(d)
    else:
        block[c] = [d]
        
    if d in block.keys():
        block[d].append(c)
    else:
        block[d] = [c]
        
ans = [0] * n
for i in range(n):
    print(i+1)
    person = i+1
    checked_person = set()
    checked_person.add(person)
    if person in friendship.keys():
        candidate = deque(friendship[person])
        while len(candidate)>0:
            c = deque.popleft(candidate)
            checked_person.add(c)
            if c not in friendship[person]:
                if person in block.keys():
                    if c not in block[person]:
                        ans[i] += 1
                else:
                    ans[i] += 1
            if c in friendship.keys():
                for p in friendship[c]:
                    if p not in checked_person and p not in candidate:
                        candidate.append(p)
    else:
        continue
                
answer = ''
for i in range(len(ans)):
    answer += str(ans[i])
    if i != n-1:
        answer += ' '
            
print(answer)

Submission status: Wrong Answer

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

for _ in range(M):
    i,j=map(int,input().split())
    graph_data[i-1][j-1]=graph_data[j-1][i-1]=1
for _ in range(K):
    i,j=map(int,input().split())
    block_data[i-1][j-1]=block_data[j-1][i-1]=1

from collections import deque

def bfs(start, W):
    work_queue = deque([])
    visited = set()
    work_queue.append(start)
    visited.add(start)
    while work_queue:
        here = work_queue.popleft()
        for i, node in enumerate(W[here]):
            if node ==0: continue
            if i not in visited:
                work_queue.append(i)
                visited.add(i)

    return visited

ans=[0]*N
for i in range(N):
    for j in bfs(i,graph_data):
        if graph_data[i][j]==0:
            ans[i]+=1
        if block_data[i][j]==1:
            ans[i]-=1
pri=''
for i in range(N):
    pri+=str(ans[i])
    if i!=N-1:
        pri+=' '
print(pri)

Submission status: Wrong Answer

Solution code:
#!/bin/bash
""":"
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 \
   /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/g.inp"
exit $?
"""
import sys


def _ia(offset=0): return [int(x) + offset for x in sys.stdin.readline().strip().split()]


def main():
    n, m, k = _ia()
    ab = []
    g = [i for i in range(n)]
    for _ in range(m):
        i, j = _ia(-1)
        ab.append([i, j])
    #
    ng = 0
    while True:
        for abi in ab:
            i, j = abi
            g[i] = g[j] = min(g[i], g[j])
        nxt = max(g) + 1
        if ng == nxt: break
        ng = nxt
    for _ in range(k):
        ab.append(_ia(-1))

    dg = [0] * ng
    for gi in g: dg[gi] += 1
    #
    r = [0] * n
    for abi in ab:
        i, j = abi
        gi, gj = g[i], g[j]
        if gi == gj:
            r[i] += 1
            r[j] += 1
    return " ".join([str(dg[g[i]] - r[i] - 1) for i in range(n)])


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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
# input = sys.stdin.buffer.readline
def input(): return sys.stdin.readline().rstrip()

class UnionFind():
    """ Union-Find木の実装（ランクあり） """
    def __init__(self, n):
        self.n = n
        self.parent = [-1]*(n+1)    # parent 親 マイナスだったら根で、絶対値が集合の数
        self.rank   = [0]*(n+1)     # rank 深さ

    def root(self, x):
        """ 木の根を求める """
        if self.parent[x] < 0:      # xが根
            return x
        else:
            self.parent[x] = self.root(self.parent[x])  # 経路圧縮
            return self.parent[x]
            
    def unite(self, x, y):
        """ xとyの属する集合を併合 """
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return 0
        elif self.rank[x] > self.rank[y]:
            self.parent[x] += self.parent[y]
            self.parent[y] = x
        else:
            self.parent[y] += self.parent[x]
            self.parent[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def isSame(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.root(x) == self.root(y) or x==y
    
    def size(self, x):
        """ xと同じ集合に属する数 """
        return -self.parent[self.root(x)]

N, M, K = map(int, input().split())
# friend = [[0]*N for _ in range(N)]
friend = defaultdict(lambda : 1)
uf = UnionFind(N)
for i in range(M):
    A, B = map(int, input().split())
    friend[A] += 1
    friend[B] += 1
    uf.unite(A, B)

# block = [[0]*N for _ in range(N)]
block = defaultdict(int)
for j in range(K):
    C, D = map(int, input().split())
    block[C] += 1
    block[D] += 1

ans = [0] * (N+1)
for i in range(1, N+1):
    ans[i] = uf.size(i) - friend[i] - block[i]
print(*ans[1:])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**5)
def bfs(ind):
    kouho=friends[ind]
    for i in kouho:
        if sans[i]!=-1:
            continue
        sans[i]=sans[ind]
        l[sans[ind]].append(i)
        bfs(i)
n,m,k=list(map(int,input().split()))
f=[list(map(int,input().split())) for _ in range(m)]
friends=[set() for _ in range(n)]
friends_num=list(map(lambda x:len(x),friends))
bl=[list(map(int,input().split())) for _ in range(k)]
l=[[] for i in range(n)]

for each in f:
    a,b=each
    friends[a-1].add(b-1)
    friends[b-1].add(a-1)

block=[set() for _ in range(n)]
for each in bl:
    a,b=each
    block[a-1].add(b-1)
    block[b-1].add(a-1)

sans=[-1 for _ in range(n)]
sans[0]=0
bfs(0)
for i in range(n):
    if sans[i]!=-1:
        continue
    sans[i]=i
    bfs(i)
ans=[0 for _ in range(n)]
for i in range(n):
    l[i]=set(l[i])


for i in range(n):
    tmp=l[sans[i]]-(block[i]|friends[i]|{i})
    ans[i]=len(tmp)


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

Submission status: Wrong Answer

Solution code:
#!/bin/bash
""":"
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 \
   /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/g.inp"
exit $?
"""
import sys


def _ia(offset=0): return [int(x) + offset for x in sys.stdin.readline().strip().split()]


def main():
    n, m, k = _ia()
    ab = []
    g = [i for i in range(n)]
    for _ in range(m):
        i, j = _ia(-1)
        ab.append([i, j])
    #
    for _ in range(17):
        for abi in ab:
            i, j = abi
            g[i] = g[j] = min(g[i], g[j])
    for _ in range(k):
        ab.append(_ia(-1))

    ng = max(g) + 1
    dg = [0] * ng
    for gi in g: dg[gi] += 1
    #
    r = [0] * n
    for abi in ab:
        i, j = abi
        gi, gj = g[i], g[j]
        if gi == gj:
            r[i] += 1
            r[j] += 1
    return " ".join([str(dg[g[i]] - r[i] - 1) for i in range(n)])


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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**5)
def bfs(ind):
    kouho=friends[ind]
    for i in kouho:
        if sans[i]!=-1:
            continue
        sans[i]=sans[ind]
        l[sans[ind]].append(i)
        bfs(i)
n,m,k=list(map(int,input().split()))
f=[list(map(int,input().split())) for _ in range(m)]
friends=[set() for _ in range(n)]
friends_num=list(map(lambda x:len(x),friends))
bl=[list(map(int,input().split())) for _ in range(k)]
l=[[] for i in range(n)]

for each in f:
    a,b=each
    friends[a-1].add(b-1)
    friends[b-1].add(a-1)

block=[set() for _ in range(n)]
for each in bl:
    a,b=each
    block[a-1].add(b-1)
    block[b-1].add(a-1)

sans=[-1 for _ in range(n)]
sans[0]=0
bfs(0)
for i in range(n):
    if sans[i]!=-1:
        continue
    sans[i]=i
    bfs(i)
ans=[0 for _ in range(n)]
for i in range(n):
    l[i]=set(l[i])
for i in range(n):
    tmp=l[i]-block[i]-friends[i]-{i}
    ans[i]=len(tmp)


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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**5)
def bfs(ind):
    kouho=friends[ind]
    for i in kouho:
        if sans[i]!=-1:
            continue
        sans[i]=sans[ind]
        l[sans[ind]].append(i)
        bfs(i)
n,m,k=list(map(int,input().split()))
f=[list(map(int,input().split())) for _ in range(m)]
friends=[set() for _ in range(n)]
friends_num=list(map(lambda x:len(x),friends))
bl=[list(map(int,input().split())) for _ in range(k)]
l=[[] for i in range(n)]

for each in f:
    a,b=each
    friends[a-1].add(b-1)
    friends[b-1].add(a-1)

block=[set() for _ in range(n)]
for each in bl:
    a,b=each
    block[a-1].add(b-1)
    block[b-1].add(a-1)

sans=[-1 for _ in range(n)]
sans[0]=0
bfs(0)
for i in range(n):
    if sans[i]!=-1:
        continue
    sans[i]=i
    bfs(i)
ans=[0 for _ in range(n)]

for i in range(n):
    tmp=(set(l[sans[i]])-block[i])-friends[i]-{i}
    ans[i]=len(tmp)


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

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]  # 親
        self.rank = [1] * n  # 深さ
        self.size = [1] * n  # size[i]はiを根とするグループのサイズ

    def find(self, x):  # xの親を返す
        if self.par[x] == x:
            return x
        else:
            return self.find(self.par[x])

    def unite(self, x, y):  # x,yの属する集合をマージする
        x = self.find(x)
        y = self.find(y)
        if x != y:
            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(self, x, y):  # x,yが同じ集合に属するか判定する
        return self.find(x) == self.find(y)

    def group_size(self, x):  # xが属する集合の大きさを返す
        return self.size[self.find(x)]


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

# 全部 0-indexed に合わせる

g_direct =[[] for _ in range(N)]
uf = UnionFind(N)  # 友達関係をまとめた UnionFind 木

for i in range(M):
    A[i], B[i] = map(int, input().split())
    A[i] -= 1
    B[i] -= 1
    g_direct[A[i]].append(B[i])
    g_direct[B[i]].append(A[i])
    uf.unite(A[i], B[i])

for i in range(K):
    C[i], D[i] = map(int, input().split())
    C[i] -= 1
    D[i] -= 1
    g_direct[C[i]].append(D[i])
    g_direct[D[i]].append(C[i])


ans = [0] * N
for i in range(N):
    ans[i] = uf.group_size(i) - len(g_direct[i]) - 1
print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**5)
def bfs(ind):
    kouho=friends[ind]
    for i in kouho:
        if sans[i]!=-1:
            continue
        sans[i]=sans[ind]
        l[sans[ind]].append(i)
        bfs(i)
n,m,k=list(map(int,input().split()))
f=[list(map(int,input().split())) for _ in range(m)]
friends=[set() for _ in range(n)]
friends_num=list(map(lambda x:len(x),friends))
bl=[list(map(int,input().split())) for _ in range(k)]
l=[[] for i in range(n)]

for each in f:
    a,b=each
    friends[a-1].add(b-1)
    friends[b-1].add(a-1)

block=[set() for _ in range(n)]
for each in bl:
    a,b=each
    block[a-1].add(b-1)
    block[b-1].add(a-1)

sans=[-1 for _ in range(n)]
sans[0]=0
bfs(0)
for i in range(n):
    if sans[i]!=-1:
        continue
    sans[i]=i
    bfs(i)
ans=[0 for _ in range(n)]
"""
for i in range(n):
    tmp=(l[sans[i]]-block[i])-friends[i]-{i}
    ans[i]=len(tmp)

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

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 get(self):
      return [self.members(r) for r in self.roots()][1:]

N,M,K = map(int,input().split())
f_arr = [[] for _ in range(N+1)]
uf = UnionFind(N+1)
for i in range(M):
  a,b = map(int,input().split())
  uf.union(a,b)
  f_arr[a].append(b)
  f_arr[b].append(a)
for j in range(K):
  a,b = map(int,input().split())
  f_arr[a].append(b)
  f_arr[b].append(a)

for k in range(1,N+1):
  print(len(uf.members(k))-len(f_arr[k]) -1)

Submission status: Wrong Answer

Solution code:

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1] * (n + 1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0] * (n + 1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if (self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]

    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if (x == y):
            return
            # 違う木に属していた場合rnkを見てくっつける方を決める
        elif (self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if (self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

    def members(self, x):
        root = self.Find_Root(x)
        return [i for i in range(self.n) if self.Find_Root(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.root) 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 size(self, x):
        return -self.root[self.Find_Root(x)]


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

uf = UnionFind(n)
directcount = [0] * n

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    directcount[a] += 1
    directcount[b] += 1
    uf.Unite(a, b)

res = []
for _ in range(n):
    res.append( [0, -1] )
ures = []

for i in range(n):
    res[i][0] = uf.size(i) - directcount[i] -1
    res[i][1] = uf.Find_Root(i)
print(res)


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


print(" ".join(list(map(lambda x: str(x[0]), res))))

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

N, M, K = map(int, input().split())
FRIENDS = [list(map(int, input().split())) for _ in range(M)]
BLOCKS = [list(map(int, input().split())) for _ in range(K)]

def search(i, friends):
    copied_friends = deepcopy(friends)
    res = []
    for a, b in friends:
        if a == i:
            copied_friends.remove([a, b])
            res.append(b)    
        if b == i:
            copied_friends.remove([a, b])
            res.append(a)
    
    return res, copied_friends

    
def find(i, j, friends):
    for a, b in friends:
        if a == i and b == j:
            return True
        if b == i and a == j:
            return True
    
    return False

    
def dfs(i, friends):
    if len(friends) == 0:
        return [i]

    targets, new_friends = search(i, friends)
    for t in targets:
        if targets.count(t) <= 1:
            targets += dfs(t, new_friends)
        
    return targets


results = []
for i in range(1, N+1):
    targets = list(set(dfs(i, FRIENDS)))
    targets = filter(lambda x: not find(x, i, FRIENDS), targets)
    targets = filter(lambda x: not find(x, i, BLOCKS), targets)

    results.append(len(list(targets)))

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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())
friends = [set(map(int, input().split())) for _ in range(M)]
blocks = [set(map(int, input().split())) for _ in range(K)]

fc = defaultdict(int)
bc = defaultdict(int)
uf = UnionFind(N)
for a, b in friends:
    uf.union(a - 1, b - 1)
    fc[a - 1] += 1
    fc[b - 1] += 1

for c, d in blocks:
    bc[c - 1] += 1
    bc[d - 1] += 1

ans = ""
for i in range(N):
    ans += str(uf.size(i) - fc[i] - bc[i] -1) + " "
print(ans.strip())

Submission status: Wrong Answer

Solution code:

class UnionFindTree():
    # Union find tree
    # 2つの効率化　経路圧縮、ランク
    # つなげることはできるか分離することはできないので、木をつなげる方向に利用する
    # 
    def __init__(self, node_size):
        # node_num: 全体のノード数
        # parent: ノードがrootなら-1、親がいれば親の番号を入れる
        # size:
        # rank:  
        # self.parent =[-1] * node_size
        self.parent =[node for node in range(node_size)]
 
        self.size = [1] * node_size
        self.rank = [1] * node_size
    
    def find_root(self,node):
        # node属する木のrootを探す
        # たどった経路に含まれるnodeの親をrootにつなぎ替える
        if self.parent[node] == node:             # 自身がrootの場合
            root = node
        else:                                   # 自身がrootでない場合
            root = self.find_root(self.parent[node]) # 再帰的にrootを探す
            self.parent[node] = root            # たどった経路に含まれるnodeの親をrootにつなぎ替える(経路圧縮)
        return root

    def unite(self,node0, node1):
        # node0とnode1が含まれる木を結合する
        
        #node0 node1のrootを求める
        root_node0 = self.find_root(node0) 
        root_node1 = self.find_root(node1)

        if root_node0 != root_node1:
            # rankを比較しrankが小さい方の木を大きい方の木のrootにつなげる
            # rank is sameのときのみrankが増える
            if self.rank[root_node0] == self.rank[root_node1]: # rank is same
                self.parent[root_node1] = root_node0
                self.rank[root_node0] += 1
            elif self.rank[root_node0] > self.rank[root_node1]:
                self.parent[root_node1] = root_node0
            else:
                self.parent[root_node0] = root_node1

            self.size[root_node0] += self.size[root_node1]

    # def recombind(self,node):
    #     # rootがnodeのものを整理し直す


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

ut = UnionFindTree(N)
friend_dict = {i:[] for i in range(N)}
friend_dict = {i:0 for i in range(N)}

for i in range(M):
    x,y = map(int,input().split())
    x-=1
    y-=1
    ut.unite(x,y)
    friend_dict[x]+=1
    friend_dict[y]+=1
    # friend_dict[x].extend([y])
    # friend_dict[y].extend([x])

for i in range(N):
    ut.find_root(i)

block_dict = {i:[] for i in range(N)}
block_dict = {i:0 for i in range(N)}

for i in range(K):
    x,y = map(int,input().split())
    x-=1
    y-=1
    if ut.parent[x]==ut.parent[y]:
        block_dict[x]+=1
        block_dict[y]+=1
        # block_dict[x].extend([y])
        # block_dict[y].extend([x])

ans =""
for i in range(N):
    group =  ut.parent[i]
    group_size = ut.size[group]

    # cand = group_size - len(friend_dict[i]) - len(block_dict[i])
    cand = group_size - friend_dict[i] - block_dict[i] - 1
    ans += str(cand) + " "
print(ans[:-1])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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 check():
    N,M,K = map(int, input().split())
    uf = UnionFind(N)
    friend = defaultdict(int)
    block = defaultdict(int)
    
    for _ in range(M):
        a,b = map(int, input().split())
        friend[a-1] += 1
        friend[b-1] += 1
        uf.union(a-1,b-1)
    
    for _ in range(K):
        a,b = map(int, input().split())
        if uf.same(a-1,b-1):
            block[a-1] += 1
            block[b-1] += 1
    
    result = [uf.size(i) - friend[i] - block[i] - 1 for i in range(N)]
    print(' '.join(map(str, result)))

Submission status: Wrong Answer

Solution code:
n, m, k = map(int, input().split())
table = [[0 for i in range(n+1)] for j in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    table[min(a,b)][max(a,b)] = 1
for i in range(k):
    c, d = map(int, input().split())
    table[max(c,d)][min(c,d)] = -1

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

for i in range(1, n+1):
    for j in range(i+1, n+1):
        check = 0
        if table[i][j] == 0 and table[j][i] != -1:
            for k in range(i, j-1):
                if table[k][k+1] != 1 or table[k+1][k] == -1:
                    check = 1
            if check == 0:
                ans[i-1] += 1
                ans[j-1] += 1
for i in ans:
    print(i, end = " ")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n, m, k = map(int, input().split())
a = [0] * m
b = [0] * m
c = [0] * k
d = [0] * k

friends = defaultdict(set)
block = defaultdict(set)

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

    friends[a[i]].add(b[i])
    friends[b[i]].add(a[i])

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

    block[c[i]].add(d[i])
    block[d[i]].add(c[i])

c = 0
party = {}
for i in range(m):
    if a[i] in party and b[i] in party:
        if party[a[i]] != party[b[i]]:
            # merge
            for k, v in party.items():
                if v == party[b[i]]:
                    party[k] = party[a[i]]
    elif a[i] in party and b[i] not in party:
        party[b[i]] = party[a[i]]
    elif a[i] not in party and b[i] in party:
        party[a[i]] = party[b[i]]
    else:
        party[a[i]] = c
        party[b[i]] = c
        c += 1

group = [set() for _ in range(c)]
for k, v in party.items():
    group[v].add(k)

anss = []
for i in range(n):
    if i not in party:
        print("0")
        continue

    gn = party[i]
    
    ans = len(group[gn])
    ans -= 1   # myself
    ans -= len(group[gn] & friends[i])
    ans -= len(group[gn] & block[i])
    anss.append(str(ans))
print(' '.join(anss))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n, m, k = map(int, input().split())
a = [0] * m
b = [0] * m
c = [0] * k
d = [0] * k

friends = defaultdict(set)
block = defaultdict(set)

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

    friends[a[i]].add(b[i])
    friends[b[i]].add(a[i])

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

    block[c[i]].add(d[i])
    block[d[i]].add(c[i])

c = 0
party = {}
for i in range(m):
    if a[i] in party and b[i] in party:
        if party[a[i]] != party[b[i]]:
            # merge
            for k, v in party.items():
                if v == party[b[i]]:
                    party[k] = party[a[i]]
    elif a[i] in party and b[i] not in party:
        party[b[i]] = party[a[i]]
    elif a[i] not in party and b[i] in party:
        party[a[i]] = party[b[i]]
    else:
        party[a[i]] = c
        party[b[i]] = c
        c += 1

group = [set() for _ in range(c)]
for k, v in party.items():
    group[v].add(k)

anss = []
for i in range(n):
    if i not in party:
        print("0")
        continue

    gn = party[i]
    
    ans = len(group[gn])
    ans -= 1   # myself
    ans -= len(group[gn] & friends[i])
    ans -= len(group[gn] & block[i])
    anss.append(str(ans))
print(friends)
print(block)
print(group)
print(' '.join(anss))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Mar  1 21:49:06 2020

@author: H_Hoshigi
"""

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

friend_set_list = []
friend_list = [[] for i in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    friend_list[A-1].append(B)
    friend_list[B-1].append(A)
    exist_set = False
    for j in friend_set_list:
        if A in j:
            j.add(B)
            exist_set = True
        if B in j:
            j.add(A)
            exist_set = True
    if exist_set == False:
        friend_set_list.append({A, B})

block_list = [[] for i in range(N)]
#Cがブロックしている人のリストがC-1番目に来る。
for i in range(K):
    C, D = map(int, input().split())
    block_list[C-1].append(D)
    block_list[D-1].append(C)

answer_list = [0 for i in range(N)]
for i in range(1, N+1):
    exist_set = False
    for j in friend_set_list:
        if i in j:
            answer_list[i-1] = len(j)-1
            for k in friend_list[i-1]:
                if k in j:
                    answer_list[i-1] -= 1
            for k in block_list[i-1]:
                if k in j:
                    answer_list[i-1] -= 1
            exist_set = True
    if exist_set == False:
        answer_list[i-1] = 0

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