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:
# 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)

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


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):
#     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]) - set(direct_friend[n]) - set(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())

friend = [[1 for i in range(n)] for j in range(n)]
for i in range(n):
  friend[i][i] = 0

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

print(" ".join([str(sum(friend[i])) for i in range(n)]))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
def root(uft, x):
    if uft[x] == x: return x
    uft[x] = root(uft, uft[x])
    return uft[x]

def same(uft, x, y):
    return root(uft, x) == root(uft, y)

def answer():
    n, m, k = map(int, input().split())
    friend = defaultdict(set)
    block = defaultdict(set)
    group = defaultdict(set)
    uft = [i for i in range(n+1)]
    for i in range(m):
        a, b = map(int, input().split())
        friend[a].add(b)
        friend[b].add(a)
    for j in range(k):
        c, d = map(int, input().split())
        block[c].add(d)
        block[d].add(c)
    for i in range(1, n+1):
        for j in friend[i]:
            uft[j] = root(uft, i)
    for i in range(1, n+1):
        uft[i] = root(uft, i)
    for i in range(1, n+1):
        group[uft[i]].add(i)
    return ' '.join(str(len(group[uft[i]]-friend[i]-block[i])-1) for i in range(1, n+1))

print(answer())

Submission status: Wrong Answer

Solution code:
# ABC157d


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    # 再帰関数を使わない限りPypyで出すこと

    class UnionFind:
        def __init__(self, n):
            self.tree = [i for i in range(n)]
            self.member = [1]*n

        def root(self, x):
            if(self.tree[x] == x):
                return x
            self.tree[x] = self.root(self.tree[x])
            return self.tree[x]  # 経路圧縮

        def same(self, x, y):  # xとyが同じ木に属するか
            return self.root(x) == self.root(y)

        def unite(self, x, y):
            x = self.root(x)
            y = self.root(y)
            if(x == y):
                return
            new = self.member[x]+self.member[y]
            self.member[x] = new
            self.member[y] = new
            self.tree[x] = y

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

    friend = [set() for i in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        friend[a - 1].add(b - 1)
        friend[b - 1].add(a - 1)
        tree.unite(a-1, b-1)
    block = [set() for i in range(n)]
    for _ in range(k):
        c, e = map(int, input().split())
        if tree.same(c - 1, e - 1):
            block[c - 1].add(e - 1)
            block[e - 1].add(c - 1)
    ans = []
    for i in range(n):
        print(i, tree.member[tree.root(i)], len(friend[i]), len(block[i]))
        ans.append(tree.member[tree.root(i)]-len(friend[i])-len(block[i])-1)
    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

candidates = [0] * n
friends = [set() for _ in range(n)]
groups = [i for i in range(n)]
blocks = [set() for _ in range(n)]

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

for i in range(n):
    for j in friends[i]:
        m = min(groups[i], groups[j])
        groups[i] = m
        groups[j] = m

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

# print(friends)
# print(groups)
# print(blocks)

groups2 = [set() for _ in range(max(groups) + 1)]
for i in range(n):
    groups2[groups[i]].add(i)

# print(groups2)
for i in range(n):
    s = set()
    s = s | groups2[groups[i]]
    s = s - friends[i]
    zibun = set()
    zibun.add(i)
    s = s - zibun
    # print(s)
    s = s - blocks[i]
    # print(s)
    candidates[i] = str(len(s))

print(' '.join(candidates))

Submission status: Wrong Answer

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
#import math

#N=int(input())
#X,Y=map(int,input().split())
#S=list(map(int,input().split()))
#S=[list(map(int,input().split())) for i in range(N)]


def segfunc(x,y):
    return (sum([x,y]))
ide_ele = 0
def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res



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)]
tomodati=[set() for i in range(N+1)]
block=[set() for i in range(N+1)]
for a,b in AB:
    tomodati[a].add(b)
    tomodati[b].add(a)
for a,b in CD:
    block[a].add(b)
    block[b].add(a)
tomodatilst=[0 for i in range(N)]
for i in range(1,N):
    if i+1 in tomodati[i]:
        tomodatilst[i]=1

n=N
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
for i in range(1,N):
    update(i,tomodatilst[i])

#print(seg)
lst=[]


biglst=set([i for i in range(1,N+1)])
for i in range(1,N+1):
    count=0
    for m in list(biglst-tomodati[i]-block[i]-set([i])):

        i,m=min(i,m),max(i,m)
        #print(i,m,query(i,m))
        if m-i==query(i,m):
            count+=1
    lst.append(count)
print(" ".join(list(map(str,lst))))

Submission status: Wrong Answer

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

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

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

def main():
  n, m, k = map(int, input().split())
  uf = UnionFind(n+1)
  F = [[] for _ in range(n+1)]
  for _ in range(m):
    a, b = map(int, input().split())
    F[a].append(b)
    F[b].append(a)
    uf.unite(a, b)
  G = [set() for _ in range(n+1)]
  for _ in range(k):
    c, d = map(int, input().split())
    G[c].add(d)
    G[d].add(c)
  for i in range(1, n+1):
    temp = set()
    for v in F[i]:
      temp |= set(uf.members(v))
    l = len(temp)
    for v in G[i]:
      if v in temp:
        l -= 1
    print(l-1-len(F[i]))
    
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.ranks = [0] * 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.ranks[x] < self.ranks[y]:
            self.parents[x] = y
        else:
            self.parents[y] = x
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x]+=1

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

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

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

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

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

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

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

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

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

def tup(a,b):
    return (min(a,b),max(a,b))

def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):
    friends = set()
    group = UnionFind(N)
    for i in range(M):
        friends.add(tup(A[i]-1,B[i]-1))
        group.union(A[i]-1,B[i]-1)
    for i in range(K):
        friends.add(tup(C[i]-1,D[i]-1))
    result = ""
    isFirst = True
    roots = group.roots()
    rootSets = {r: [] for r in roots }
    for i in range(N):
        r = group.find(i)
        rootSets[r].append(i)
    for i in range(N):
        c = 0
        r = group.find(i)
        # for g in rootSets[r]:
        #     if g != i and tup(i,g) not in friends:
        #         c+= 1
        if not isFirst:
            result+=" "
        else:
            isFirst = False
        result+=str(c)
    print(result)
    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:
import sys
from collections import defaultdict, Counter


class UnionFind(object):
    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 main():
    n, m, k = list(map(int, sys.stdin.readline().strip().split()))

    friends = defaultdict(set)
    blocks = defaultdict(set)

    for i in range(m):
        a, b = list(map(int, sys.stdin.readline().strip().split()))
        a -= 1
        b -= 1
        friends[a].add(b)
        friends[b].add(a)

    for i in range(k):
        c, d = list(map(int, sys.stdin.readline().strip().split()))
        c -= 1
        d -= 1
        blocks[c].add(d)
        blocks[d].add(c)

    uf = UnionFind(n)

    for f_key in friends:
        for child in friends[f_key]:
            # child_cur_group = parents[child]
            uf.union(f_key, child)

    group_num_set = defaultdict(set)
    for i in range(n):
        group = uf.find(i)
        group_num_set[group].add(i)
    #
    # ans = [0] * n
    # for i in range(n):
    #     group = uf.find(i)
    #     friend_cand = group_num_set[group]
    #     true_friend_cand = friend_cand.difference(blocks[i]).difference(friends[i])
    #     ans[i] = len(true_friend_cand) - 1
    #
    # return ans
    return [0]


result = main()
print(' '.join([str(num) for num in result]))

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, Counter


class UnionFind(object):
    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 main():
    n, m, k = list(map(int, sys.stdin.readline().strip().split()))

    friends = defaultdict(set)
    blocks = defaultdict(set)

    for i in range(m):
        a, b = list(map(int, sys.stdin.readline().strip().split()))
        a -= 1
        b -= 1
        friends[a].add(b)
        friends[b].add(a)

    for i in range(k):
        c, d = list(map(int, sys.stdin.readline().strip().split()))
        c -= 1
        d -= 1
        blocks[c].add(d)
        blocks[d].add(c)

    uf = UnionFind(n)

    for f_key in friends:
        for child in friends[f_key]:
            # child_cur_group = parents[child]
            uf.union(f_key, child)

    # group_num_set = defaultdict(set)
    # for i in range(n):
    #     group = uf.find(i)
    #     group_num_set[group].add(i)
    #
    # ans = [0] * n
    # for i in range(n):
    #     group = uf.find(i)
    #     friend_cand = group_num_set[group]
    #     true_friend_cand = friend_cand.difference(blocks[i]).difference(friends[i])
    #     ans[i] = len(true_friend_cand) - 1
    #
    # return ans
    return [0]


result = main()
print(' '.join([str(num) for num in result]))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
def root(uft, x):
    if uft[x] == x: return x
    uft[x] = root(uft, uft[x])
    return uft[x]

def same(uft, x, y):
    return root(uft, x) == root(uft, y)

def answer():
    n, m, k = map(int, input().split())
    friend = defaultdict(set)
    block = defaultdict(set)
    group = defaultdict(set)
    uft = [i for i in range(n+1)]
    for i in range(m):
        a, b = map(int, input().split())
        friend[a].add(b)
        friend[b].add(a)
    for j in range(k):
        c, d = map(int, input().split())
        block[c].add(d)
        block[d].add(c)
    for i in range(1, n+1):
        for j in friend[i]:
            uft[j] = root(uft, i)
    for i in range(1, n+1):
        group[root(uft, i)].add(i)
    return ' '.join(str(len(group[root(uft, i)]-friend[i]-block[i])-1) for i in range(1, n+1))

print(answer())

Submission status: Wrong Answer

Solution code:
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d=[float("inf")]*n #各頂点への距離
    used=[False]*n
    d[s]=0
    
    while True:
        v=-1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v==-1): #その頂点が使われたかチェック
                v=i			            #まだなら仮確定
            elif (not used[i]) and d[i]<d[v]: #より距離が近いのがあればそちらから
                v=i
        if v==-1:
             break
        used[v]=True
               
        for j in range(n):
            d[j]=min(d[j],d[v]+cost[v][j])
    return d

################################
n,m,k=map(int,input().split()) #n:頂点数　m:辺の数 k:ブロック関係の数

cost=[[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
block=[[None for i in range(n)] for i in range(n)] 
for i in range(m): #友人関係
    x,y=map(int,input().split())
    cost[x-1][y-1]=1
    block[x-1][y-1]=True
    cost[y-1][x-1]=1
    block[y-1][x-1]=True

for i in range(k): #ブロック関係
    x,y=map(int,input().split())
    block[x-1][y-1]=False
    block[y-1][x-1]=False
print(block)
ans=[]
for i in range(n):
    dijk=dijkstra(i,n,m,cost)
    for x,j in enumerate(block[i]): #blockから各リスト取り出す
        if j==False or j==True:
            dijk[x]=0
    cnt=0
    for i in dijk:
        if i>0 and i!=float('inf'):
            cnt+=1
    ans.append(cnt)
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
            break
    if not con:
        return 0
    for f in F[j]:
        if f in c:
            continue
        c.add(f)
        if f not in F[i] and f not in B[i]:
            s+=1
        s+=dps(i,f,c)
    return s
for i in range(0,N):
    checked=set()
    print(dps(i, i, checked)-1, end=" ")

Submission status: Wrong Answer

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.ranks = [0] * 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.ranks[x] < self.ranks[y]:
            self.parents[x] = y
        else:
            self.parents[y] = x
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x]+=1

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

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

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

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

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

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

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

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

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

def tup(a,b):
    return (min(a,b),max(a,b))

def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):
    friends = defaultdict(bool)
    group = UnionFind(N)
    for i in range(M):
        friends[tup(A[i]-1,B[i]-1)] = True
        group.union(A[i]-1,B[i]-1)
    for i in range(K):
        friends[tup(C[i]-1,D[i]-1)] = True
    result = ""
    isFirst = True
    roots = group.roots()
    rootSets = {r: set() for r in roots }
    for i in range(N):
        r = group.find(i)
        rootSets[r].add(i)
    # for i in range(N):
    #     c = 0
    #     r = group.find(i)
    #     for g in rootSets[r]:
    #         if g != i and not friends[tup(i,g)]:
    #             c+= 1
    #     if not isFirst:
    #         result+=" "
    #     else:
    #         isFirst = False
    #     result+=str(c)
    print(result)
    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:
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
            break
    if not con:
        return 0
    for f in F[j]:
        if f in c:
            continue
        c.add(f)
        if f not in F[i] and f not in B[i]:
            s+=1
        s+=dps(i,f,c)
    return s
print(F, B)
for i in range(0,N):
    checked=set()
    print(dps(i, i, checked)-1, end=" ")

Submission status: Wrong Answer

Solution code:
N,M,K = map(int,input().split())
f = [[] for i in range(N)]
h = [[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    f[a-1].append(b-1)
    f[b-1].append(a-1)

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


for i in range(N):
    c = 0
    p = 0
    for j in range(i,N):
        if j+1 in f[j]:
            c += 1
        else:
            break
    for k in range(i,-1,-1):
        if k-1 in f[k]:
            p += 1
        else:
            break
    n = c + p
    n -= sum(x >= i-p and x <= i+c for x in f[i])
    n -= sum(x >= i-p and x <= i+c for x in h[i])
    print(n,end=' ')

Submission status: Wrong Answer

Solution code:
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d=[float("inf")]*n #各頂点への距離
    used=[False]*n
    d[s]=0
    
    while True:
        v=-1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v==-1): #その頂点が使われたかチェック
                v=i			            #まだなら仮確定
            elif (not used[i]) and d[i]<d[v]: #より距離が近いのがあればそちらから
                v=i
        if v==-1:
             break
        used[v]=True
               
        for j in range(n):
            d[j]=min(d[j],d[v]+cost[v][j])
    return d

################################
n,m,k=map(int,input().split()) #n:頂点数　m:辺の数 k:ブロック関係の数

cost=[[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
block=[[None for i in range(n)] for i in range(n)] 
for i in range(m): #友人関係
    x,y=map(int,input().split())
    cost[x-1][y-1]=1
    block[x-1][y-1]=True
    cost[y-1][x-1]=1
    block[y-1][x-1]=True

for i in range(k): #ブロック関係
    x,y=map(int,input().split())
    block[x-1][y-1]=False
    block[y-1][x-1]=False
print(block)
ans=[]
for i in range(n):
    dijk=dijkstra(i,n,m,cost)
    print(i+1,dijk)

    for x,j in enumerate(block[i]): #blockから各リスト取り出す
        if j==False or j==True:
            dijk[x]=0
    cnt=0
    for i in dijk:
        if i>0 and i!=float('inf'):
            cnt+=1
    ans.append(cnt)
print(*ans)

Submission status: Wrong Answer

Solution code:
n,m,k=[int(i) for i in input().split(" ")]

list=[]
for i in range(1,n+1):
    for j in range(i+1,n+1):
        list.append([i,j])
fri=[]
for j in range(m):
    x,y=[int(i) for i in input().split(" ")]
    if x>y:
        x,y=y,x
    fri.append([x,y])

blo=[]
for j in range(k):
    x,y=[int(i) for i in input().split(" ")]
    if x>y:
        x,y=y,x
    blo.append([x,y])

res=[]
for i in list:
    if not i in blo and not i in fri:
        res.append(i)
friend=[0 for i in range(n)]
for i in res:
    friend[i[0]-1]+=1
    friend[i[1]-1]+=1

for i in friend:
    print(str(i)+" ",end="")
print()

Submission status: Wrong Answer

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math

import itertools

#import bisect

import copy
from functools import lru_cache

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]



def main():
    n,m,k=map(int,input().split())
    re=[set() for _ in range(n)]
    bl=[set() for _ in range(n)]
#    print(re)
    for i in range(m):
        a,b=map(int,input().split())
        re[a-1].add(b)
        re[b-1].add(a)
    for i in range(k):
        a,b=map(int,input().split())
        bl[a-1].add(b)
        bl[b-1].add(a)
    cl=copy.deepcopy(re)
    for i in range(n):
        for j in cl[i]:
            cl[i]=cl[i].union(cl[j-1])
    for i in range(n-1,-1,-1):
        for j in cl[i]:
            cl[i]=cl[i].union(cl[j-1])
#    print(cl)

    for i in range(n):
        cl[i]=cl[i].symmetric_difference(re[i])
        cl[i]=cl[i].union(bl[i])
        cl[i]=cl[i].symmetric_difference(bl[i])
    ans=""
#    print(cl)
    for i in range(n):
        ans=ans+str(len(cl[i])-1)+" "
    print(ans)


if __name__ == "__main__":
    main()