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

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)]


#xの木の根を求める
def root(x,li): 
    if li[x] == x:
        return x
    else:
        li[x] = root(li[x],li)
        return li[x]

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

#xとｙを併合
def union(x,y,li):
    x = root(x,li)
    y = root(y,li)
    if x==y:
        return
    else:
        li[x] = 1

li1 = [i for i in range(N)]
li2 = [i for i in range(N)]

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    union(a-1,b-1,li1)
for i in range(K):
    c = CD[i][0]
    d = CD[i][1]
    union(c-1,d-1,li2)

mm = [0 for i in range(max(li1))]
for i in range(N):
    m = root(i,li1)
    mm[m-1] += 1

# print(li1)
# print(mm)
ans = [mm[li1[i]-1]-1 for i in range(N)]
# print(ans)

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    ans[a-1] -= 1
    ans[b-1] -= 1


for i in range(K):
    c = CD[i][0]
    d = CD[i][1]
    if find(c-1,d-1,li1):
        ans[c-1] -= 1
        ans[d-1] -= 1
print(*ans)

Submission status: Wrong Answer

Solution code:
import sys

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)]


#xの木の根を求める
def root(x,li): 
    if li[x] == x:
        return x
    else:
        li[x] = root(li[x],li)
        return li[x]

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

#xとｙを併合
def union(x,y,li):
    x = root(x,li)
    y = root(y,li)
    if x==y:
        return
    

li1 = [i for i in range(N)]
li2 = [i for i in range(N)]

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    union(a-1,b-1,li1)
for i in range(K):
    c = CD[i][0]
    d = CD[i][1]
    union(c-1,d-1,li2)

mm = [0 for i in range(max(li1))]
for i in range(N):
    m = root(i,li1)
    mm[m-1] += 1

# print(li1)
# print(mm)
ans = [mm[li1[i]-1]-1 for i in range(N)]
# print(ans)

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    ans[a-1] -= 1
    ans[b-1] -= 1


for i in range(K):
    c = CD[i][0]
    d = CD[i][1]
    if find(c-1,d-1,li1):
        ans[c-1] -= 1
        ans[d-1] -= 1
print(*ans)

Submission status: Wrong Answer

Solution code:
n,m,k = [int(x) for x in input().split()]
tomo = list()
for i in range(m):
    tomo.append([int(x) for x in input().split()])
block = list()
for i in range(k):
    block.append([int(x) for x in input().split()])

for i in range(1,n+1):
    count =0
    for j in tomo:
        if (i in j):
            count += 1
    for k in block:
        if (i in k):
            count += 1
    print(n-1-count,end=" ")

Submission status: Wrong Answer

Solution code:
import sys

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)]


#xの木の根を求める
def root(x,li): 
    if li[x] == x:
        return x
    else:
        li[x] = root(li[x],li)
        return li[x]

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

#xとｙを併合
def union(x,y,li):
    x = root(x,li)
    y = root(y,li)
    

li1 = [i for i in range(N)]
li2 = [i for i in range(N)]

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    union(a-1,b-1,li1)
for i in range(K):
    c = CD[i][0]
    d = CD[i][1]
    union(c-1,d-1,li2)

mm = [0 for i in range(max(li1))]
for i in range(N):
    m = root(i,li1)
    mm[m-1] += 1

# print(li1)
# print(mm)
ans = [mm[li1[i]-1]-1 for i in range(N)]
# print(ans)

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    ans[a-1] -= 1
    ans[b-1] -= 1


for i in range(K):
    c = CD[i][0]
    d = CD[i][1]
    if find(c-1,d-1,li1):
        ans[c-1] -= 1
        ans[d-1] -= 1
print(*ans)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     

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 and not i in self.block[x] and not i in self.friend[x]]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

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

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

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

def main():
    N, M, K = LI()
    uf = UnionFind(N)
    G = [[] for _ in range(N)]
    block = [set() for _ in range(N)]
    friend = [set() for _ in range(N)]

    for _ in range(M):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)
        uf.union(a, b)
        friend[a].add(b)
        friend[b].add(a)

    for _ in range(K):
        a, b = LI_()
        block[a].add(b)
        block[b].add(a)
    ans = [0 for _ in range(N)]
    for i in range(N):
        q = [i]
        visited = [0 for _ in range(N)]
        visited[i] = 1
        _ans = 0
        while q:
            v = q.pop()
            for next_v in G[v]:
                if visited[next_v]:
                    continue
                if next_v in block[i] or next_v in friend[i]:
                    pass
                else:
                    print('i: ', i, ' next_v: ', next_v)
                    _ans += 1
                visited[next_v] = 1
                q.append(next_v)
        ans[i] = _ans
    for i in range(N):
        print(ans[i], end=' ')
    print()

    '''
    uf.block = block
    uf.friend = friend
    for i in range(N):
        print(len(uf.members(i)) - 1, end=' ')
    print()
    '''
main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

black = [[] for _ in range(N)]
for _ in range(K):
    C, D = map(lambda s: int(s)-1, input().split())
    black[C].append(D)
    black[D].append(C)

#print(white, black)

ans = [0 for _ in range(N)]

def freinds(i):
    visit = [False for _ in range(N)]
    visit[i] = True

    Q = deque()
    Q.append(white[i])
    while Q:
        for q in Q.popleft():
            #print('q', q, i, visit)
            if visit[q]:
                continue
            else:
                Q.append(white[q])
                if q not in white[i] and q not in black[i]:
                    ans[i] += 1
                visit[q] = True
                #print('cnt')

for i in range(N):
    freinds(i)

print(ans)

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)]
n,m,k=map(int,input().split())
a=[0]*m
b=[0]*m
c=[0]*k
d=[0]*k
g=UnionFind(n)
h=UnionFind(n)
cnt=[0]*n
for i in range(m):
    a[i],b[i]=map(int,input().split())
    g.Unite(a[i],b[i])
    cnt[a[i]-1]+=1
    cnt[b[i]-1]+=1
for j in range(k):
    c[j],d[j]=map(int,input().split())
    #cnt[c[j]-1]-=1
    #cnt[d[j]-1]-=1
    h.Unite(c[j],d[j])
    if g.isSameGroup(c[j],d[j]):
        continue
    else:
        cnt[c[j]-1]-=1
        cnt[d[j]-1]-=1
ans=[0]*n
for i in range(n):
    ans[i]=max(0,g.Count(i+1)-h.Count(i+1)-cnt[i])
    ans[i]=str(ans[i])
    #print(g.Count(i+1),h.Count(i+1))
print(' '.join(ans))

Submission status: Wrong Answer

Solution code:
N,M,K = map(int,input().split())
AB = []
for _ in range(M):
    AB.append([int(i) for i in input().split()])
CD = []
for _ in range(K):
    CD.append([int(i) for i in input().split()])
from collections import defaultdict as ddict
friend = ddict(list)
for ab in AB:
    friend[ab[0]].append(ab[1])
    friend[ab[1]].append(ab[0])
block = ddict(list)
for cd in CD:
    block[cd[0]].append(cd[1])
    block[cd[1]].append(cd[0])
from collections import deque
group = []
done = set()
for n in range(1,N):
    if n in done:
        pass
    else:
        group.append([])
        q = deque([n])
        while q:
            target = q.pop()
            for f in friend[target]:
                if f not in group[-1]:
                    q.append(f)
                    group[-1].append(f)
                    done.add(f)
group_fix = []
for g in group:
    group_fix.append(set(g))
ans = []
for n in range(1,N+1):
    for g in group_fix:
        if n in g:
            temp = g - set(block[n])
            ans_temp = len(temp) - 1 - len(friend[n])
            if ans_temp < 0:
                ans_temp = 0
            ans.append(ans_temp)
            break
        else:
            pass
print(*ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#def find_friend(tree_node, target):
#    for friend in tree_node.friends:
#        if target in friend.friend_numbers:
#            return True
#
#    flags = []
#    for friend in tree_node.friends:
#        flags.append(find_friend(friend, target))
#    if True in flags:
#        return True
#    return False

def display(node):
        print('----')
        print('val: {}'.format(node.val))
        print('friend_numbers: {}'.format(node.friend_numbers))
        print('block_numbers: {}'.format(node.block_numbers))

def find_friend(root, target):
    queue = [root]
    already_list = [root.val]
    while len(queue) > 0:
        node = queue.pop(0)
        if target in node.friend_numbers:
            return True
        
        for friend in node.friends:
            if friend.val not in already_list:
                queue.append(friend)
                already_list.append(friend.val)

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.friends = []
        self.friend_numbers = []
        self.blocks = []
        self.block_numbers = []
        self.candidate = []

[N, M, K] = [int(i) for i in input().split()]

AB = []
for m in range(M):
    [a, b] = [int(i) for i in input().split()]
    AB.append((a, b))

CD = []
for k in range(K):
    [c, d] = [int(i) for i in input().split()]
    CD.append((c, d))

tree_nodes = {}
for i in range(1, N + 1):
    tree_node = TreeNode(i)
    tree_nodes[i] = tree_node

for (a, b) in AB:
    tree_nodes[a].friends.append(tree_nodes[b])
    tree_nodes[a].friend_numbers.append(b)
    tree_nodes[b].friends.append(tree_nodes[a])
    tree_nodes[b].friend_numbers.append(a)

for (c, d) in CD:
    tree_nodes[c].blocks.append(tree_nodes[d])
    tree_nodes[c].block_numbers.append(d)
    tree_nodes[d].blocks.append(tree_nodes[c])
    tree_nodes[d].block_numbers.append(c)

for k, v in tree_nodes.items():
    display(v)

candidates = []
for k, v in tree_nodes.items():
    # 友達候補を探す
    candidate = 0
    for n in range(1, N + 1):
        if n == k:
            continue
        if n in v.friend_numbers:
            continue
        if n in v.block_numbers:
            continue

        # nさんへの友達経路があるか探索
        flag = find_friend(v, n)
        if flag:
            candidate += 1
        print('{}の友達候補{}: {}'.format(k, n, flag))
    
    candidates.append(candidate)

ans = ''
for candidate in candidates:
    ans += str(candidate)
    ans += ' '

print(ans[:len(ans)-1])

Submission status: Wrong Answer

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

FList = [[] for i in range(N)]
BList = [[] for i in range(N)]

FFList = [[] * N]
for i in range(M):
    A, B = map(int, input().split())
    
    FList[A - 1].append(B - 1)
    FList[B - 1].append(A - 1)
    
for i in range(K):
    C, D = map(int, input().split())
    
    BList[C - 1].append(D - 1)
    BList[D - 1].append(C - 1)
    
for i in range(N):
    print((N - 1) - (len(FList[i]) + len(BList[i])), end=" ")

Submission status: Wrong Answer

Solution code:
N,M,K = map(int,input().split())
AB = []
for _ in range(M):
    AB.append([int(i) for i in input().split()])
CD = []
for _ in range(K):
    CD.append([int(i) for i in input().split()])
from collections import defaultdict as ddict
friend = ddict(list)
for ab in AB:
    friend[ab[0]].append(ab[1])
    friend[ab[1]].append(ab[0])
block = ddict(list)
for cd in CD:
    block[cd[0]].append(cd[1])
    block[cd[1]].append(cd[0])
from collections import deque
group = []
done = set()
for n in range(1,N):
    if n in done:
        pass
    else:
        group.append([])
        q = deque([n])
        while q:
            target = q.pop()
            for f in friend[target]:
                if f not in group[-1]:
                    q.append(f)
                    group[-1].append(f)
                    done.add(f)
group_fix = []
for g in group:
    group_fix.append(set(g))
ans = []
for n in range(1,N+1):
    for g in group_fix:
        if n in g:
            temp = g - set(block[n])
            ans.append(len(temp) - 1 - len(friend[n]))
            break
        else:
            pass
print(*ans)

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, M, K = LI()
AB = []
CD = []
for i in range(M):
    a,b = LI()
    a -= 1
    b -= 1
    AB.append([a,b])
for k in range(K):
    c, d = LI()
    c -= 1
    d -= 1
    CD.append([c,d])
direct_friend = {}
blocked = {}
relation = [[] for i in range(N)]
for i in range(N):
    direct_friend[i] = []
    blocked[i] = []
for i in range(M):
    a,b = AB[i]
    direct_friend[a].append(b)
    direct_friend[b].append(a)
for i in range(K):
    c,d = CD[i]
    blocked[c].append(d)
    blocked[d].append(c)

def dfs(node, p, cluster):
    cluster.append(node)
    if direct_friend[node] == [p]:
        return cluster
    for new_node in direct_friend[node]:
        if new_node == p:continue
        elif new_node in cluster:continue
        else:
            return dfs(new_node, node, cluster)

for i in range(N):
    if len(relation[i]) == 0:
        cluster = dfs(i, -1, [])
        # print(cluster)
        if cluster == None:
            relation[i] = []
        else:   
            for j in cluster:
                relation[j] = cluster

# print(relation)
# print(direct_friend)
# print(blocked)

for i in range(N):
    blocked[i] = set(blocked[i])
    direct_friend[i] = set(direct_friend[i])

# for i in range(N):
#     if len(direct_friend[n]) == 0:

ans = []
for n in range(N):
    # print(set(relation[n]) - set(direct_friend[n]) - set(blocked[n]) - set([n]))
    ans.append(len(set(relation[n]) - direct_friend[n] - blocked[n] - set([n])))

for a in ans:
    print(max(a, 0), end = " ")
print("")

Submission status: Wrong Answer

Solution code:
n, m, k = list(map(int, input().split()))
ms = {}
for _ in range(m):
    a, b = list(map(int, input().split()))
    ms[a] = ms.get(a, set())
    ms[a].add(b)
    ms[b] = ms.get(b, set())
    ms[b].add(a)

ks = {}
for _ in range(k):
    c, d = list(map(int, input().split()))
    ks[c] = ks.get(c, set())
    ks[c].add(d)
    ks[d] = ks.get(d, set())
    ks[d].add(c)

num_cand = []
for i in range(1, n+1):
    cnt = len([j for j in range(1, n+1)
               if j != i and \
               (j not in ms or i not in ms[j]) and \
               (j not in ks or i not in ks[j])
               ])
    num_cand.append(str(cnt))
print(" ".join(num_cand))

Submission status: Wrong Answer

Solution code:
import sys

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)]


#xの木の根を求める
def root(x,li): 
    if li[x] == x:
        return x
    else:
        li[x] = root(li[x],li)
        return li[x]

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

#xとｙを併合
def union(x,y,li):
    x = root(x,li)
    y = root(y,li)
    if x==y:
        return
    else:
        li[x] = y

li1 = [i for i in range(N)]
li2 = [i for i in range(N)]
sys.exit()
for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    union(a-1,b-1,li1)
# for i in range(K):
#     c = CD[i][0]
#     d = CD[i][1]
#     union(c-1,d-1,li2)

mm = [0 for i in range(max(li1))]
for i in range(N):
    m = root(i,li1)
    mm[m-1] += 1

# print(li1)
# print(mm)
ans = [mm[li1[i]-1]-1 for i in range(N)]
# print(ans)

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    ans[a-1] -= 1
    ans[b-1] -= 1


for i in range(K):
    c = CD[i][0]
    d = CD[i][1]
    if find(c-1,d-1,li1):
        ans[c-1] -= 1
        ans[d-1] -= 1
print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000)

def addfrends(friends):
    global ff
    if len(friends-ff) != 0:
        new = friends - ff
        #print(friends-ff)
        ff |= friends
        for person in new:
            addfrends(people[person][0])

n,m,k = map(int,input().split())
people = [[set(),set()] for _ in range(n+1)]
#print(people)
ans = []
for _ in range(m):
    a,b = map(int,input().split())
    people[a][0].add(b)
    people[b][0].add(a)
for _ in range(k):
    a,b = map(int,input().split())
    people[a][1].add(b)
    people[b][1].add(a)
for friends,blocked in people:
    ff = set()
    addfrends(friends)
    #print(ff - blocked - friends)
    ans.append(len(ff - blocked - friends)-1)
ans.pop(0)
print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)

n, m, k = map(int, input().split())
ab = [tuple(map(int,input().split())) for i in range(m)]
cd = [tuple(map(int,input().split())) for i in range(k)]
es1 = [[] for i in range(n)]
for i, (a,b) in enumerate(ab):
    a,b = a-1,b-1
    es1[a].append(b)
    es1[b].append(a)

es2 = [[] for i in range(n)]
for i, (c,d) in enumerate(cd):
    c,d = c-1,d-1
    es2[c].append(d)
    es2[d].append(c)

ans = [0]*n

for i in range(n):
    visited = [False] * n
    i_good = es1[i]
    i_bad = es2[i]
    visited
    queue = deque()
    queue.extend(i_good)

    while len(queue):
        next_ = queue.pop()
        if visited[next_] == False:
            if (not next_ in i_good) and (not next_ in i_bad):
                ans[i] += 1
            visited[next_] = True
            queue.extend(es1[next_])

    ans[i] -= 1

print(*ans, sep=' ')

Submission status: Wrong Answer

Solution code:
class UnionFindByRank():
  def __init__(self, n):
    self.parents = list(range(n))
    self.rank = [0] * 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 union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
      return

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


if __name__ == '__main__':
  N, M, K = list(map(int, input().split()))
  uf = UnionFindByRank(N + 1)
  #A, B, C, D = [0] * M, [0] * M, [0] * K, [0] * K
  friends = set()
  blocks = set()
  for i in range(M):
    # friends
    #A[i], B[i] = list(map(int, input().split()))
    pair = tuple(sorted(map(int, input().split())))
    friends.add(pair)
    uf.union(pair[0], pair[1])
  for i in range(K):
    # blocks
    blocks.add(tuple(sorted(map(int, input().split()))))

res = [0] * N

for i in range(1, N):
  cnt = 0
  for j in range(i + 1, N + 1):
    if i != j and uf.find(i) == uf.find(j) and \
            not tuple(sorted([i, j])) in blocks and \
            not tuple(sorted([i, j])) in friends:
      cnt += 1
  res[i - 1] += cnt
  res[j - 1] += cnt

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

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, M, K = LI()
AB = []
CD = []
for i in range(M):
    a,b = LI()
    a -= 1
    b -= 1
    AB.append([a,b])
for k in range(K):
    c, d = LI()
    c -= 1
    d -= 1
    CD.append([c,d])
direct_friend = {}
blocked = {}
relation = [0 for i in range(N)]
for i in range(N):
    direct_friend[i] = []
    blocked[i] = []
for i in range(M):
    a,b = AB[i]
    direct_friend[a].append(b)
    direct_friend[b].append(a)
for i in range(K):
    c,d = CD[i]
    blocked[c].append(d)
    blocked[d].append(c)




def dfs(node, p, cluster):
    cluster.append(node)
    if direct_friend[node] == [p]:
        return cluster
    for new_node in direct_friend[node]:
        if new_node == p:continue
        elif new_node in cluster:continue
        else:
            return dfs(new_node, node, cluster)

for i in range(N):
    if relation[i] == 0:
        cluster = dfs(i, -1, [])
        # print(cluster)
        if cluster == None:
            relation[i] = []
        else:   
            for j in cluster:
                relation[j] = cluster

# print(relation)
# print(direct_friend)
# print(blocked)

for i in range(N):
    blocked[i] = set(blocked[i])
    direct_friend[i] = set(direct_friend[i])

# for i in range(N):
#     if len(direct_friend[n]) == 0:

ans = []
for n in range(N):
    # print(set(relation[n]) - set(direct_friend[n]) - set(blocked[n]) - set([n]))
    ans.append(len(set(relation[n]) - direct_friend[n] - blocked[n] - set([n])))

for a in ans:
    print(max(a, 0), end = " ")
print("")

Submission status: Wrong Answer

Solution code:
n, m, k = map(int, input().split())
N = [[] for _ in range(n)]

for _ in range(m):
    tmp1, tmp2 = map(int, input().split())
    tmp1 -= 1; tmp2 -= 1
    N[tmp1].append(tmp2)
    N[tmp2].append(tmp1)

for _ in range(k):
    tmp1, tmp2 = map(int, input().split())
    tmp1 -= 1; tmp2 -= 1
    N[tmp1].append(tmp2)
    N[tmp2].append(tmp1)

for fr in N:
    print(n-len(fr)-1, end=' ')

Submission status: Wrong Answer

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


def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):
    par = list(range(N))
    rank = [0] * N

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

    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return

        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

    def same(x, y):
        return par[x] == par[y]

    friend = collections.defaultdict(set)
    for i in range(M):
        a = A[i] - 1
        b = B[i] - 1
        unite(a, b)
        friend[a].add(b)
        friend[b].add(a)

    block = collections.defaultdict(set)
    for i in range(K):
        c = C[i] - 1
        d = D[i] - 1
        block[c].add(d)
        block[d].add(c)

    tomodatinowa = [0] * N
    for i in range(N):
        tomodatinowa[par[i]] += 1

    res = [0] * N
    for i in range(N):
        res[i] = tomodatinowa[par[i]] - 1
        for bl in block[i]:
            if same(i, bl):
                res[i] -= 1
        for fr in friend[i]:
            if same(i, fr):
                res[i] -= 1

    print(" ".join(str(a) for a in res))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    C = [int()] * (K)  # type: "List[int]"
    D = [int()] * (K)  # type: "List[int]"
    for i in range(K):
        C[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, K, A, B, C, D)


if __name__ == '__main__':
    main()

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)]
AB.sort()
CD.sort()
friend=[N-1]*N
anti=[]
ans=[]
count = 1
cnt=1
#print(AB)
#print(CD)
m=0
n=0
while m<M:
    friend[AB[m][0]-1]-=1
    friend[AB[m][1]-1]-=1
    m+=1
while n<K:
    friend[CD[n][0]-1]-=1
    friend[CD[n][1]-1]-=1
    n+=1
"""for i in range(M-1):
    if AB[i][0]==AB[i+1][0]:
        count+=1
    else:
        friend[AB[i][0]]-=count
        count=1
for j in range(K-1):
    if CD[j][0]==CD[j+1][0]:
        cnt+=1
    else:
        friend[CD[j][0]]-=cnt
        cnt=1
while True:
    if len(friend)<N:
        friend.append([0,0])
        break
while True:
    if len(anti)<K:
        anti.append([0,0])
        break"""

print(*friend)
"""while m<len(friend):
    if friend[m]==
print(ans)"""

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2000000)
N,M,K=map(int,input().split())
F=[set() for i in range(N)]
for _ in range(M):
    a,b=map(int,input().split())
    F[a-1].add(b-1)
    F[b-1].add(a-1)
B=[set() for i in range(N)]
for _ in range(K):
    c,d=map(int,input().split())
    B[c-1].add(d-1)
    B[d-1].add(c-1)

def dps(i, j, c):
    s=0
    con=False
    for f in F[j]:
        if f not in c:
            con=True
            c.add(f)
            if f not in F[i] and f not in B[i]:
                s+=1
            s+=dps(i,f,c)
    if not con:
        return 0
    else:
        return s
for i in range(0,N):
    checked=set()
    print(dps(i, i, checked)-1, end=" ")