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 itertools
import math
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from functools import reduce

sys.setrecursionlimit(4100000)
from functools import lru_cache

INF = 1 << 60

#Union Find
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())
direct = [[0 for j in range(n)] for i in range(n)]
# print(direct)
uf = UnionFind(n)
# print(uf)
for i in range(m + k):
    a, b = map(int, input().split())
    direct[a - 1][b - 1] = 1
    direct[b - 1][a - 1] = 1
    if i < m:
        uf.union(a - 1, b - 1)
print(uf)
print(direct)
for i in range(n):
    ans = 0
    for j in range(n):
        if i == j:
            continue
        if direct[i][j] == 0 and uf.same(i, direct[i][j]):
            ans += 1
    print("%d " % ans, end="")

Submission status: Wrong Answer

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

label = [0] * n
kosu_label = 1

block = [0] * n

ans = [0] * n

for i in range(m):
    a[i], b[i] = map(int, input().split())
    
for i in range(k):
    c[i], d[i] = map(int, input().split())
    
friend = [[] for i in range(n)]
    
for i in range(n):
   for j in range(m):
       if a[j] == i + 1:
           friend[i].append(b[j])
       elif  b[j] == i + 1:
           friend[i].append(a[j])

for i in range(n):
    if label[i] == 0:
        label[i] = kosu_label
    for j in range(len(friend[i])):
        if label[friend[i][j] - 1] == 0:
            label[friend[i][j] - 1] = label[i]
        elif label[friend[i][j] - 1] != label[i]:
            label[i] = min(label[friend[i][j] - 1], label[i])
            label[friend[i][j] - 1] = min(label[friend[i][j] - 1], label[i])
            
    kosu_label = kosu_label + 1    

label_s = [0] * kosu_label

for i in range(n):
    label_s[label[i]] = label_s[label[i]] + 1
    


for w in range(k):
    if label[c[w] - 1] == label[d[w] - 1]:
        block[c[w] - 1] = block[c[w] - 1] + 1
        block[d[w] - 1] = block[d[w] - 1] + 1
            
for i in range(n):
    ans[i] = label_s[label[i]] - len(friend[i]) - block[i] - 1

for i in range(n):
    print(ans[i], end = ' ')

Submission status: Wrong Answer

Solution code:
n, m, k = map(int, input().split())
f = [n - 1 for i in range(n)]
for i in range(m + k):
    a, b = map(int, input().split())
    f[a - 1] -= 1
    f[b - 1] -= 1
print(' '.join(map(str, f)))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
N,M,K=map(int,input().split())
F=[[] for i in range(N)]
for _ in range(M):
    A,B=map(int,input().split())
    F[A-1].append(B-1)
    F[B-1].append(A-1)
B=[[] for i in range(N)]
for _ in range(K):
    C,D=map(int,input().split())
    B[C-1].append(D-1)
    B[D-1].append(C-1)
G=[i for i in range(N)]
def root(i):
    if G[i]==i:
        return i
    else:
        a=root(G[i])
        G[i]=a
        return a
def union(i,j):
    x=root(i)
    y=root(j)
    if x==y:
        return
    else:
        G[y]=x
        return
for i in range(N):
    for f in F[i]:
        union(i, f)
group={}
for i in range(N):
    if G[i] in group:
        group[G[i]]+=1
    else:
        group[G[i]]=1
for i in range(N):
    ans=group[G[i]]
    for f in F[i]:
        if root(i)==root(f):
            ans-=1
    for b in B[i]:
        if root(i)==root(b):
            ans-=1
    print(ans-1, end=" ")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
N,M,K=map(int,input().split())
F=[[] for i in range(N)]
for _ in range(M):
    A,B=map(int,input().split())
    F[A-1].append(B-1)
    F[B-1].append(A-1)
B=[[] for i in range(N)]
for _ in range(K):
    C,D=map(int,input().split())
    B[C-1].append(D-1)
    B[D-1].append(C-1)
ans=[0 for i in range(N)]
seen=[False for i in range(N)]
n=0
G=[i for i in range(N)]
def root(i):
    if G[i]==i:
        return i
    else:
        a=root(G[i])
        G[i]=a
        return a
def union(i,j):
    x=root(i)
    y=root(j)
    if x==y:
        return
    else:
        if x>y:
            x,y=y,x
        G[y]=x
        return
for i in range(N):
    for f in F[i]:
        union(i, f)
group={}
for i in range(N):
    if G[i] in group:
        group[G[i]]+=1
    else:
        group[G[i]]=1
for i in range(N):
    ans=group[G[i]]
    for f in F[i]:
        if root(i)==root(f):
            ans-=1
    for b in B[i]:
        if root(i)==root(b):
            ans-=1
    print(ans-1, end=" ")

Submission status: Wrong Answer

Solution code:
N,M,K=map(int,input().split())
F=[[] for i in range(N)]
for _ in range(M):
    A,B=map(int,input().split())
    F[A-1].append(B-1)
    F[B-1].append(A-1)
B=[[] for i in range(N)]
for _ in range(K):
    C,D=map(int,input().split())
    B[C-1].append(D-1)
    B[D-1].append(C-1)
ans=[0 for i in range(N)]
seen=[False for i in range(N)]
n=0
G=[i for i in range(N)]
def root(i):
    if G[i]==i:
        return i
    else:
        a=root(G[i])
        G[i]=a
        return a
def union(i,j):
    x=root(i)
    y=root(j)
    if x==y:
        return
    else:
        if x>y:
            x,y=y,x
        G[y]=x
        return
for i in range(N):
    for f in F[i]:
        union(i, f)
group={}
for i in range(N):
    if G[i] in group:
        group[G[i]]+=1
    else:
        group[G[i]]=1
for i in range(N):
    ans=group[G[i]]
    for f in F[i]:
        if root(i)==root(f):
            ans-=1
    for b in B[i]:
        if root(i)==root(b):
            ans-=1
    print(ans-1, end=" ")

Submission status: Wrong Answer

Solution code:
def make_label(x, y, a, b, label, m):
    h = False
    g = []
    for i in range(m):
        if a[i] == x and label[b[i] - 1] == 0:
            label[b[i] - 1] = y
            g.append(b[i])
            h = True
        elif b[i] == x and label[a[i] - 1] == 0:
            label[a[i] - 1] = y
            h = True
            g.append(a[i])
        
    if h:
        for i in range(len(g)):
            return make_label(g[i], y, a, b, label, m)
    else:
        return label  
        


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

label = [0] * n
kosu_label = 1

friend = [0] * n
block = [0] * n

ans = [0] * n

for i in range(m):
    a[i], b[i] = map(int, input().split())
    
for i in range(k):
    c[i], d[i] = map(int, input().split())
    
for i in range(n):
    if label[i] == 0:
        label[i] = kosu_label
        label = make_label(i + 1, kosu_label, a, b, label, m)
        kosu_label = kosu_label + 1

label_s = [0] * kosu_label

for i in range(n):
    label_s[label[i]] = label_s[label[i]] + 1
    

for j in range(m):
    friend[a[j] - 1] = friend[a[j] - 1] + 1
    friend[b[j] - 1] = friend[b[j] - 1] + 1
for w in range(k):
    if label[c[w] - 1] == label[d[w] - 1]:
        block[c[w] - 1] = block[c[w] - 1] + 1
        block[d[w] - 1] = block[d[w] - 1] + 1
            
for i in range(n):
    ans[i] = label_s[label[i]] - friend[i] - block[i] - 1

for i in range(n):
    print(ans[i], end = ' ')

Submission status: Wrong Answer

Solution code:
def make_label(x, y, a, b, label, m):
    h = False
    g = []
    for i in range(m):
        if a[i] == x and label[b[i] - 1] == 0:
            label[b[i] - 1] = y
            g.append(b[i])
            h = True
        elif b[i] == x and label[a[i] - 1] == 0:
            label[a[i] - 1] = y
            h = True
            g.append(a[i])
        
    if h:
        for i in range(len(g)):
            return make_label(g[i], y, a, b, label, m)
    else:
        return label  
        


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

label = [0] * n
kosu_label = 1

friend = [0] * n
block = [0] * n

ans = [0] * n

for i in range(m):
    a[i], b[i] = map(int, input().split())
    
for i in range(k):
    c[i], d[i] = map(int, input().split())
    
for i in range(n):
    if label[i] == 0:
        label[i] = kosu_label
        label = make_label(i + 1, kosu_label, a, b, label, m)
        kosu_label = kosu_label + 1
        
print(label)

label_s = [0] * kosu_label

for i in range(n):
    label_s[label[i]] = label_s[label[i]] + 1
    
for i in range(n):
    for j in range(m):
        if a[j] == i + 1 or b[j] == i + 1:
            friend[i] = friend[i] + 1
    for w in range(k):
        if (c[w] == i + 1 or d[w] == i + 1) and label[c[w] - 1] == label[d[w] - 1]:
            block[i] = block[i] + 1
    ans[i] = label_s[label[i]] - friend[i] - block[i] - 1

for i in range(n):
    print(ans[i], end = ' ')

Submission status: Wrong Answer

Solution code:
def make_label(x, y, a, b, label, m):
    h = False
    g = []
    for i in range(m):
        if a[i] == x and label[b[i] - 1] == 0:
            label[b[i] - 1] = y
            g.append(b[i])
            h = True
        elif b[i] == x and label[a[i] - 1] == 0:
            label[a[i] - 1] = y
            h = True
            g.append(a[i])
        
    if h:
        for i in range(len(g)):
            return make_label(g[i], y, a, b, label, m)
    else:
        return label  
        


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

label = [0] * n
kosu_label = 1

friend = [0] * n
block = [0] * n

ans = [0] * n

for i in range(m):
    a[i], b[i] = map(int, input().split())
    
for i in range(k):
    c[i], d[i] = map(int, input().split())
    
for i in range(n):
    if label[i] == 0:
        label[i] = kosu_label
        label = make_label(i + 1, kosu_label, a, b, label, m)
        kosu_label = kosu_label + 1

label_s = [0] * kosu_label

for i in range(n):
    label_s[label[i]] = label_s[label[i]] + 1
    
for i in range(n):
    for j in range(m):
        if a[j] == i + 1 or b[j] == i + 1:
            friend[i] = friend[i] + 1
    for w in range(k):
        if (c[w] == i + 1 or d[w] == i + 1) and label[c[w] - 1] == label[d[w] - 1]:
            block[i] = block[i] + 1
    ans[i] = label_s[label[i]] - friend[i] - block[i] - 1

for i in range(n):
    print(ans[i], end = '')

Submission status: Wrong Answer

Solution code:
def make_label(x, y, a, b, label, m):
    h = False
    g = []
    for i in range(m):
        if a[i] == x and label[b[i] - 1] == 0:
            label[b[i] - 1] = y
            g.append(b[i])
            h = True
        elif b[i] == x and label[a[i] - 1] == 0:
            label[a[i] - 1] = y
            h = True
            g.append(a[i])
        
    if h:
        for i in range(len(g)):
            return make_label(g[i], y, a, b, label, m)
    else:
        return label  
        


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

label = [0] * n
kosu_label = 1

friend = [0] * n
block = [0] * n

ans = [0] * n

for i in range(m):
    a[i], b[i] = map(int, input().split())
    
for i in range(k):
    c[i], d[i] = map(int, input().split())
    
for i in range(n):
    if label[i] == 0:
        label[i] = kosu_label
        label = make_label(i + 1, kosu_label, a, b, label, m)
        kosu_label = kosu_label + 1

label_s = [0] * kosu_label

for i in range(n):
    label_s[label[i]] = label_s[label[i]] + 1
    
print(label_s)

for i in range(n):
    for j in range(m):
        if a[j] == i + 1 or b[j] == i + 1:
            friend[i] = friend[i] + 1
    for w in range(k):
        if (c[w] == i + 1 or d[w] == i + 1) and label[c[w] - 1] == label[d[w] - 1]:
            block[i] = block[i] + 1
    ans[i] = label_s[label[i]] - friend[i] - block[i] - 1

print(friend)
print(block)

for i in range(n):
    print(ans[i], end = '')

Submission status: Wrong Answer

Solution code:
def DFS(Start, NodeList, NodeNum, SearchNode):
    if NodeNum == M:
        return NodeNum
    
    for NextNode, Connect in enumerate(g[SearchNode]):
         if Connect and NextNode not in NodeList:
                NodeList.append(NextNode)
                if not b[Start][NextNode]:
                    NodeNum += 1
                MaxNodeNum = DFS(Start, NodeList, NodeNum, NextNode)
                if MaxNodeNum > NodeNum:
                    NodeNum =  MaxNodeNum
    return NodeNum



N, M, K = tuple(map(int, input().split()))
g = [[0 for _ in range(N)] for _ in range(N)]
b = [[0 for _ in range(N)] for _ in range(N)]

for _ in range(M):
    x, y = tuple(map(int, input().split()))
    g[x-1][y-1] = 1; g[y-1][x-1] = 1
    
for _ in range(K):
    x, y = tuple(map(int, input().split()))
    b[x-1][y-1] = 1; b[y-1][x-1] = 1


ans = []
for i in range(N):
    ans.append(DFS(i, [i], 1, i) - 1 - sum(g[i]))
    
print(" ".join([str(x) for x in ans]))

Submission status: Wrong Answer

Solution code:
class Tree():
    def __init__(self, edges=None, costs=None):
        self.nodes = set()
        self.edges = dict()
        if edges is not None:
            if costs is not None:
                for e, c in zip(edges, costs):
                    self.add_edge(e, c)
            else:
                for e in edges:
                    self.add_edge(e)
        
    def __iter__(self):
        return self.edges.__iter__()
    
    def __str__(self):
        return self.edges.__str__()
    
    def __repr__(self):
        return self.edges.__repr__()
    
    def add_node(self, x):
        self.nodes.add(x)
    
    def add_edge(self, x, cost=0):
        assert len(x) == 2, '{} is not appropriate edge!'.format(x)
        a, b = (x[0], x[1]) if x[0] < x[1] else (x[1], x[0])
        assert a not in self.nodes or b not in self.nodes, '{} is a cycle edge!'.format(x)
        
        if a not in self.nodes:
            self.nodes.add(a)
        if b not in self.nodes:
            self.nodes.add(b)
        self.edges[(a, b)] = cost
    
    def degree(self, n):
        assert n in self.nodes, '{} is not appropriate node!'.format(n)
        return sum([(n in edge) for edge in self.edges])
    
    def get_edges(self, n):
        return [edge for edge in self.edges if n in edge]
    
    def get_nearby_nodes(self, n):
        return [e[1] if e[0] == n else e[0] for e in self.edges if n in e]
    
    def dps(self, root):
        nodes, stack = [], [root]
        while stack:
            current_node = stack.pop()
            assert current_node not in nodes, 'Tree has a cycle!'
                
            nodes.append(current_node)
            for n in reversed(self.get_nearby_nodes(current_node)):
                if n not in nodes:
                    stack.append(n)
        return nodes
    
    def wps(self, root):
        nodes, queue = [], deque([root])
        while queue:
            current_node = queue.popleft()
            assert current_node not in nodes, 'Tree has a cycle!'
            
            nodes.append(current_node)
            for n in self.get_nearby_nodes(current_node):
                if n not in nodes:
                    queue.append(n)
        return nodes
        
    def display(self):
        from IPython.display import SVG, display
        import networkx as nx
        
        nx_graph = nx.Graph()
        for u, v in self:
            nx_graph.add_edge(u, v)
        return SVG(nx.nx_agraph.to_agraph(nx_graph).draw(prog='fdp', format='svg'))

class Graph(Tree):
    def __init__(self, edges=None, costs=None):
        super().__init__(edges, costs)
    
    def add_edge(self, x, cost=0):
        assert len(x) == 2, '{} is not appropriate edge!'.format(x)
        a, b = (x[0], x[1]) if x[0] < x[1] else (x[1], x[0])
        
        if a not in self.nodes:
            self.nodes.add(a)
        if b not in self.nodes:
            self.nodes.add(b)
        self.edges[(a, b)] = cost 
    
    def dps(self, root):
        nodes, stack, is_cycle = [], [root], False
        while stack:
            current_node = stack.pop()
            if current_node in nodes:
                is_cycle = True
                continue
            nodes.append(current_node)
            for n in reversed(self.get_nearby_nodes(current_node)):
                if n not in nodes:
                    stack.append(n)
        return nodes, is_cycle
    
    def wps(self, root):
        nodes, queue, is_cycle = [], deque([root]), False
        while queue:
            current_node = queue.popleft()
            if current_node in nodes:
                is_cycle = True
                continue
            nodes.append(current_node)
            for n in self.get_nearby_nodes(current_node):
                if n not in nodes:
                    queue.append(n)
        return nodes, is_cycle

inputs = open(0).readlines()
n, m, k = map(int, inputs[0].split())
AB = [tuple(map(int, ab.split())) for ab in inputs[1:m+1]]
CD = [tuple(map(int, cd.split())) for cd in inputs[m+1:]]

friends = Graph(AB)
blocks = [set() for _ in range(1, n+1)]
for n0, n1 in CD:
    for i in range(1, n+1):
        if n0 == i:
            blocks[i-1].add(n1)
        elif n1 == i:
            blocks[i-1].add(n1)
*nb_friends, = map(sum, ([n0 == i or n1 == i for n0, n1 in AB] for i in range(1, n+1)))

connected_nodes = []
for i in range(1, n+1):
    if all(i not in nodes for nodes in connected_nodes):
        nodes, _ = friends.dps(i)
        connected_nodes.append(set(nodes))
nb_nodes = [len(nodes) for nodes in connected_nodes]

candidates = []
for i in range(1, n+1):
    for nodes, nb_node in zip(connected_nodes, nb_nodes):
        if i in nodes:
            candidates.append(nb_node - 1 - nb_friends[i-1] - len(nodes & blocks[i-1]))
            break
print(*candidates)

Submission status: Wrong Answer

Solution code:
n,m,k=map(int,input().split())
par=[i for i in range(n)]
rank=[0 for i in range(n)]
# this par & rank are initialized lists
def find_par(x):
    global par
    if par[x]==x:
        return x
    else:
        par[x]= find_par(par[x])
        return par[x]
def unite(x,y):
    x,y=find_par(x),find_par(y)
    global rank,par
    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 find_par(x)==find_par(y)
friend=[set() for i in range(n)]
for i in range(m):
    a,s=map(int,input().split())
    a-=1;s-=1
    unite(a,s)
    friend[a].add(s)
    friend[s].add(a)
anti=[set() for i in range(n)]
for i in range(k):
    a,b=map(int,input().split())
    a-=1;b-=1
    anti[a].add(b)
    anti[b].add(a)
friends=[set() for i in range(n)]
for i in range(n):
    friends[par[i]].add(i)
psfriend=[friends[par[i]] for i in range(n)]

print(*[len(psfriend[i]-anti[i]-friend[i]-set([i])) for i in range(n)],sep=" ")

Submission status: Wrong Answer

Solution code:
from collections import deque
n,k,m=map(int,input().split())

F=[[] for _ in range(n)]
B=[[] for _ in range(n)]

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

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


def find(i):
    dis=0
    Q=deque([[i,dis]])
    ans=0
    visited={i}
    while Q:
        f,dis=Q.pop()
        if dis>1 and not f in B[i]:
            ans+=1

        for j in F[f]:
            if j in visited:
                continue
            if b in B[f]:
                continue
            Q.appendleft([j,dis+1])
            visited.add(j)
    return ans

ANS=[]
for i in range(n):
    ANS.append(find(i))
print(*ANS)

Submission status: Wrong Answer

Solution code:
# import numpy as np
class UnionFind:
    def __init__(self, n):
        # self.parent = np.array([-1] * n)
        # self.size = np.array([1] * n)
        self.parent = [-1] * n
        self.size = [1] * n
    def find(self, x):
        if self.parent[x] == -1:
            return x
        else:
            a = self.find(self.parent[x])
            self.parent[x] = a
            return a
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            self.parent[x] = y
            self.size[y] += self.size[x]
    def get_size(self, x):
        return self.size[self.find(x)]
    def printout(self):
        print(self.parent)
        print(self.size)

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

ab = [[int(i)-1 for i in input().split()] for j in range(M)]
cd = [[int(i)-1 for i in input().split()] for j in range(K)]

# for a, b in ab:
#     uf.union(a, b)

# ans =[uf.get_size(i)-1 for i in range(N)]

# for a, b in ab:
#     ans[a] -= 1
#     ans[b] -= 1

# for c, d in cd:
#     if uf.find(c) == uf.find(d):
#         ans[c] -= 1
#         ans[d] -= 1

# print(*ans)

Submission status: Wrong Answer

Solution code:
from sys import exit, setrecursionlimit
setrecursionlimit(10**6)

def array2D(row, col ,val=0):
    return [[val]*col for i in range(row)]


class UnionFind():
	def __init__(self, N):
		self.N = N # データ数
		self.d = [-1]*N # 親の番号，根の場合は，-(集合の要素数)

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

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x==y: return False
		if self.d[x] > self.d[y]: x,y = y,x
		self.d[x] += self.d[y]
		self.d[y] = x
		return True

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

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

n,m,k = map(int, input().split())
uf_friend = UnionFind(n+1)
G = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int, input().split())
    uf_friend.union(a,b)
    G[a].append(b)
    G[b].append(a)

uf_block = UnionFind(n+1)
for i in range(k):
    a,b = map(int, input().split())
    if uf_friend.same(a,b) and (b not in G[a]):
        uf_block.union(a,b)
ans = []
for i in range(1,n+1):
    ans.append(uf_friend.size(i)-uf_block.size(i) - len(G[i]))
print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
def main(lines):
    friend = []
    block = []
    friend_dict = defaultdict(list)
    for i, v in enumerate(lines):
        if i == 0:
            N, M, K = [int(a.strip()) for a in v.split(' ')]
        elif i < M + 1:
            a, b = [int(a.strip()) for a in v.split(' ')]
            friend.append([a,b])
            friend_dict[a].append(b)
            friend_dict[b].append(a)
        else:
            c, d = [int(a.strip()) for a in v.split(' ')]
            block.append([c,d])
    
    tree_list = []
    while friend_dict != {}:
        seen = DFS(friend_dict)
        tree_list.append(seen)
        for k in seen:
            friend_dict.pop(k)

    result = {}
    for i in range(1,N+1):
        flg = 0 
        for tree in tree_list:
            if i in tree:
                result[i] = len(tree)
                flg = 1
        if flg == 0:
            result[i] = 0

    for i,j in friend:
        result[i] -= 1
        result[j] -= 1

    for i,j in block:
        for tree in tree_list:
            if j in tree and i in tree:
                    result[i] -= 1
                    result[j] -= 1  
    s_n = ' '.join([str(i-1) for i in result.values()])
    print(s_n)

def DFS(node_dict):
    p = list(node_dict.keys())[0]
    seen = [p]
    todo = [p]
    while todo != []:
        for i in todo:
            for j in node_dict[i]:
                flg =0
                if not j in seen:
                    flg = 1
                    seen.append(j)
                    todo.append(j)
                    continue
                else:
                    continue
                if flg == 0:
                    todo.remove(j)
        todo.remove(i)
    return seen
                
if __name__ == '__main__':
    lines = []
    for l in sys.stdin:
        lines.append(l.rstrip('\r\n'))
    main(lines)

Submission status: Wrong Answer

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

S = [[i,100001,[]] for i in range(1,n+1)]
count = 0
for num in range(m+k):
    i1, i2 = map(int,input().split())
    a = S[i1-1][1]
    b = S[i2-1][1]
    a_1, a_2 = -1, []
    b_1, b_2 = -1, []
    t = min(a, b)
    if t == 100001:
        a_1 = b_1 = count
        count += 1
    else:
        a_1 = b_1 = t
    
    a_2 = S[i1-1][2]; b_2 = S[i2-1][2]
    a_2.append(i2); b_2.append(i1)
    
    S[i1-1][1:] = [a_1, a_2]; S[i2-1][1:] = [b_1, b_2]
friend = ''
for i in range(0,count):
    xc = [x[1] for x in S]
    indexes = [j+1 for j, x in enumerate(xc) if x == i]
    for z in range(len(indexes)):
        S[indexes[z]-1][2].append(S[indexes[z]-1][0])
        V = S[indexes[z]-1][2]#+indexes[:z]
        result = (set(indexes) - set(V))
        S[indexes[z]-1][2].append(z)
        friend += str(len(result)) + ' '
    #print(indexes)

print(friend)

Submission status: Wrong Answer

Solution code:
N, M, K = map(int, input().split())
friend = [[] for _ in range(N+1)]
block = [[] for _ in range(N+1)]

for i in range(M):
  A,B = map(int, input().split())
  friend[A].append(B)
  friend[B].append(A)

for i in range(K):
  C,D = map(int, input().split())
  block[C].append(D)
  block[D].append(C)
#print(friend)
#print(block)

import queue
grouping = [False]*(N+1)
#print(grouping)
grouping[0] = True
group = [0]*(N+1)
g_num = 0
g_cnt = []
for i in range(1,N+1):
  cnt = 0
  if grouping[i] == True:
    continue 
  group[i] = g_num
  grouping[i] = True
  q = queue.Queue()
  q.put(i)
  while not q.empty():
    #print('v:',visited)
    p = q.get()
    for f in friend[p]:
      #print(p,f)
      if grouping[f]==False:
        q.put(f)
        group[f]=g_num
        grouping[f] =True
        cnt += 1
  g_num += 1
  g_cnt.append(cnt)
  #print('g:',grouping)
ans = []
for i in range(N+1):
  c = g_cnt[group[i]]-len(friend[i])
  for b in block[i]:
    if group[b]==group[i]:
      c -= 1
  ans.append(c)
print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = None  # 人の数
RELATION = None
NOT_FRIEND = 0
FRIEND = 1
BLOCK = 2
SELF = -1
CANDIDATE = None
CANDIDATE_COUNT = None
deq = deque()

# BLOCKを避けてFRIENDを辿って、NOT_FRIENDに行き着いたらCANDIDATE_COUNTを+1


def friend_list(i, j):
    for p in range(len(RELATION[i])):
        if p != j and \
                RELATION[i][p] is FRIEND:
            deq.append([i, p])


def dfs(i, j):  # iからjに到達可能か
    while len(deq) != 0:
        u = deq.popleft()  # フレンドを取得
        if CANDIDATE[u[1]][j]:  # 友達の友達候補の場合は友達候補
            CANDIDATE[i][j] = True
            CANDIDATE_COUNT[i] += 1
            deq.clear()
            return
        if RELATION[u[1]][j] is FRIEND or RELATION[j][u[1]] is FRIEND:  # 友達の友達は友達候補
            CANDIDATE[i][j] = True
            CANDIDATE_COUNT[i] += 1
            deq.clear()
            return
        friend_list(u[1], i)  # フレンドのフレンドじゃなければ、その人のフレンド一覧をキューに保存する
    CANDIDATE[i][j] = False


# main
if __name__ == '__main__':
    N, M, K = map(int, input().split(" "))
    RELATION = [[NOT_FRIEND] * N for i in range(N)]
    CANDIDATE = [[None] * N for i in range(N)]
    CANDIDATE_COUNT = [0 for i in range(N)]
    for i in range(N):
        RELATION[i][i] = SELF
        CANDIDATE[i][i] = False
    for i in range(M):
        a, b = map(int, input().split(" "))
        RELATION[a - 1][b - 1] = FRIEND
        RELATION[b - 1][a - 1] = FRIEND
        CANDIDATE[a - 1][b - 1] = False
        CANDIDATE[b - 1][a - 1] = False
    for i in range(K):
        c, d = map(int, input().split(" "))
        RELATION[c - 1][d - 1] = BLOCK
        RELATION[d - 1][c - 1] = BLOCK
        CANDIDATE[c - 1][d - 1] = False
        CANDIDATE[d - 1][c - 1] = False
    for i in range(N):
        friend_list(i, i)
        for j in range(N):
            if i != j:
                if RELATION[i][j] is NOT_FRIEND:
                    # (i, j)を起点としたdfsを実施
                    dfs(i, j)
        deq.clear()
    print(" ".join(map(str, CANDIDATE_COUNT)))