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:
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())
num_fri = [0] * N
union = UnionFind(N)
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    num_fri[a] += 1
    num_fri[b] += 1
    union.union(a, b)
for i in range(K):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    num_fri[a] += 1
    num_fri[b] += 1
    
for i in range(N):
    print(union.size(i) - 1 - num_fri[i], end=' ')

Submission status: Wrong Answer

Solution code:
from itertools import chain

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

bff = [list(map(int,input().split())) for i in range(m)]

blk = [list(map(int,input().split())) for i in range(k)]

for i in range(m):
    bff[i] = sorted(bff[i])

for i in range(k):
    blk[i] = sorted(blk[i])

bff = sorted(bff, key = lambda x: x[0])
blk = sorted(blk, key = lambda x: x[0])

flag = 0
V6 = [[]]
cnt = 6

a = list(chain.from_iterable(bff))
b = list(chain.from_iterable(blk))


fqua = [0] * n
bqua = [0] * n

for i in range(n):
    fqua[i] = a.count(i+1)
    bqua[i] = b.count(i+1)



for i in range(m):
    if(flag == 0):
        flag = 1
        V6[0].append(bff[0][0])
        V6[0].append(bff[0][1])
        continue
    
    for j in range(len(V6)):
        
        if((bff[i][0] in set(V6[j])) and (bff[i][1] in set(V6[j]))):
            break
        elif(bff[i][0] in set(V6[j])):            
            V6[j].append(bff[i][1])
            
            break
        elif(bff[i][1] in set(V6[j])):
            V6[j].append(bff[i][0])
            
            break
        elif(j == len(V6)-1):
            V6.append([bff[i][0],bff[i][1]])
            
            break
        
for i in range(len(V6)):
    V6[i] = set(V6[i])


for i in range(n):
    for j in V6:
        if i+1 in j:
            print(len(j) - fqua[i] - bqua[i] -1 , end=" ")
            
        else:
            print(0,end =" " )

Submission status: Wrong Answer

Solution code:
from itertools import chain

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

bff = [list(map(int,input().split())) for i in range(m)]

blk = [list(map(int,input().split())) for i in range(k)]

for i in range(m):
    bff[i] = sorted(bff[i])

for i in range(k):
    blk[i] = sorted(blk[i])

bff = sorted(bff, key = lambda x: x[0])
blk = sorted(blk, key = lambda x: x[0])

flag = 0
V6 = [[]]
cnt = 6

a = list(chain.from_iterable(bff))
b = list(chain.from_iterable(blk))


fqua = [0] * n
bqua = [0] * n

for i in range(n):
    fqua[i] = a.count(i+1)
    bqua[i] = b.count(i+1)



for i in range(m):
    if(flag == 0):
        flag = 1
        V6[0].append(bff[0][0])
        V6[0].append(bff[0][1])
        continue
    
    for j in range(len(V6)):
        
        if((bff[i][0] in set(V6[j])) and (bff[i][1] in set(V6[j]))):
            break
        elif(bff[i][0] in set(V6[j])):            
            V6[j].append(bff[i][1])
            
            break
        elif(bff[i][1] in set(V6[j])):
            V6[j].append(bff[i][0])
            
            break
        elif(j == len(V6)-1):
            V6.append([bff[i][0],bff[i][1]])
            
            break
        
for i in range(len(V6)):
    V6[i] = set(V6[i])


for i in range(n):
    for j in V6:
        if i+1 in j:
            print(len(j) - fqua[i] - bqua[i] -1 , end=" ")
            
        else:
            print(0,end =" " )
        

print(V6)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n, m, k = map(int, input().split())
friend = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
check = [0]*n
union = [-1]*n
union[0] = 0
for i in range(n):
    if check[i]: continue
    que = deque([i])
    while que:
        u = que.popleft()
        for v in friend[u]:
            if check[v]: continue
            union[v] = i
            check[v] = 1
            que.append(v)
            
brock = [[] for _ in range(n)]
for _ in range(k):
    c, d = map(int, input().split())
    if union[c-1] == union[d-1]:
        brock[c-1].append(d-1)
        brock[d-1].append(c-1)
        
ans = [0]*n
check = [0]*n
for i in range(n):
    if check[i]: continue
    que = deque([i])
    for j in range(i+1, n):
        if union[j] == union[i]: que.append(j)
    res = len(que)
    while que:
        u = que.popleft()
        check[u] = 1
        ans[u] = res-len(friend[u])-len(brock[u])-1
print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n, m, k = map(int, input().split())
friend = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
check = [0]*n
union = [-1]*n
union[0] = 0
for i in range(n):
    if check[i]: continue
    que = deque([i])
    while que:
        u = que.popleft()
        for v in friend[u]:
            if check[v]: continue
            union[v] = i
            check[v] = 1
            que.append(v)
            
brock = [[] for _ in range(n)]
for _ in range(k):
    c, d = map(int, input().split())
    if union[c-1] == union[d-1]:
        brock[c-1].append(d-1)
        brock[d-1].append(c-1)
        
ans = [0]*n
check = [0]*n
for i in range(n):
    if check[i]: continue
    que = deque([i])
    for j in range(i+1, n):
        if union[j] == union[i]: que.append(j)
    res = len(que)
    while que:
        u = que.popleft()
        check[u] = 1
        ans[u] = res-len(friend[u])-len(brock[u])-1
print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n, m, k = map(int, input().split())
friend = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
check = [0]*n
union = [-1]*n
union[0] = 0
for i in range(n):
    if check[i]: continue
    que = deque([i])
    while que:
        u = que.popleft()
        for v in friend[u]:
            if check[v]: continue
            union[v] = i
            check[v] = 1
            que.append(v)
            
brock = [[] for _ in range(n)]
for _ in range(k):
    c, d = map(int, input().split())
    if union[c-1] == union[d-1]:
        brock[c-1].append(d-1)
        brock[d-1].append(c-1)
        
ans = [0]*n
check = [0]*n
for i in range(n):
    if check[union[i]]: continue
    que = deque([i])
    for j in range(i+1, n):
        if union[j] == union[i]: que.append(j)
    res = len(que)
    while que:
        u = que.popleft()
        check[u] = 1
        ans[u] = res-len(friend[u])-len(brock[u])-1
print(*ans)

Submission status: Wrong Answer

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

N, M, K = map(int, input().split())
 
#ab = [list(map(int, input().split())) for _ in range(M)]
#cd = [list(map(int, input().split())) for _ in range(K)]
 
lstab = [[] for _ in range(N)]
lstcd = [[] for _ in range(N)]

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

for _ in range(K):
    c, d = map(int, input().split())
    lstcd[c-1].append(d-1)
    lstcd[d-1].append(c-1)
    
groups = []
visiteds = [0] * N

for i in range(N):
    if visiteds[i] == 1: continue
    temp = [i]
    visited = [i]
    visiteds[i] = 1
 
    while temp:
        x = temp.pop()
        for y in lstab[x]:
            if visiteds[y] == 1:continue
            temp.append(y)
            visited.append(y)
            visiteds[y] = 1
    groups.append(visited)
    if sum(visiteds) == 1:break
 
ans = [0] * N
for grp in groups:
    setgrp = set(grp)
    for j in grp:
        ans[j] = len(setgrp - set(lstcd[j])) - 1 - len(lstab[j])
 
print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque


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

ARR = []
BRR = []
for i in range(M):
    ARR.append(list(map(int,input().split())))

for i in range(K):
    BRR.append(list(map(int,input().split())))

#
# N = 10
# M = 9
# K = 3
# ARR = [
#     [10, 1],
#     [6, 7],
#     [8, 2],
#     [2, 5],
#     [8, 4],
#     [7, 3],
#     [10, 9],
#     [6, 4],
#     [5, 8],
#     [2, 6],
# ]
#
# BRR = [
#     [7, 5],
#     [3, 1],
# ]

def prepare(n, arr):
    nodes = [[] for i in range(n)]
    nodeStates = [False for i in range(n)]
    nodeLabels = [0 for i in range(n)]
    for ar in arr:
        fromNode = ar[0] - 1
        toNode = ar[1] - 1
        nodes[fromNode].append(toNode)
        nodes[toNode].append(fromNode)

    return nodes, nodeStates, nodeLabels

def prepare2(n,brr):
    nodes = [set() for i in range(n)]
    for ar in brr:
        fromNode = ar[0] - 1
        toNode = ar[1] - 1
        nodes[fromNode].add(toNode)

    return nodes


def calculate(n, m, k, nodes, nodeStates, nodeLabels,blockNodes):
    q = deque()

    label = 0
    labelDict = []
    while nodeStates.count(False) > 0:

        falseIndex = nodeStates.index(False)

        q.append(falseIndex)
        mmm = set()
        while len(q) > 0:
            node = q.popleft()
            if nodeStates[node] == True:
                continue
            nodeStates[node] = True
            nodeLabels[node] = label
            childNodes = nodes[node]
            mmm.add(node)
            for childNode in childNodes:
                if nodeStates[childNode] == False:
                    q.append(childNode)

        labelDict.append(mmm)
        label = label + 1

    result = []
    for i in range(n):
        l = nodeLabels[i]

        p = labelDict[l]
        pp = blockNodes[i]
        s = p & pp
        result.append(str(len(labelDict[l]) - len(nodes[i]) - 1 - len(s)))

    print(" ".join(result))


nodes, nodeStates, nodeLabels = prepare(N, ARR)
blockNodes = prepare2(N,BRR)
calculate(N, M, K, nodes, nodeStates, nodeLabels,blockNodes)

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

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())
l=[-1]*(N+1)
la=N

for i in range(M):
    if l[a[i]]<0 and l[b[i]]<0:
        l[a[i]]=la
        l[b[i]]=la
        la-=1
    elif l[a[i]]>l[b[i]]:
        if l[b[i]]>0:
            l=[x if x is not l[b[i]] else l[a[i]] for x in l ]
        else:
            l[b[i]]=l[a[i]]

    else:
        if l[a[i]] > 0:
            l = [x if x is not l[a[i]] else l[b[i]] for x in l]
        else:
            l[a[i]]=l[b[i]]

t=[]

for i in range(1,N+1):

    if l[i]>0:
        p=l.count(l[i])-1
        indexes = [j for j, x in enumerate(a) if x == i]
        for j in range(len(indexes)):
            if l[b[indexes[j]]]==l[i]:
                p-=1
        indexes = [j for j, x in enumerate(b) if x == i]
        for j in range(len(indexes)):
            if l[a[indexes[j]]] == l[i]:
                p -= 1
        indexes = [j for j, x in enumerate(d) if x == i]
        for j in range(len(indexes)):
            if l[c[indexes[j]]] == l[i]:
                p -= 1
        indexes = [j for j, x in enumerate(c) if x == i]
        for j in range(len(indexes)):
            if l[d[indexes[j]]] == l[i]:
                p -= 1


    else:
        p=0
    t.append(p)
print(t)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


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, readline().split())
ab = [list(map(int, readline().split())) for _ in range(m)]
cd = [list(map(int, readline().split())) for _ in range(k)]
graph = [[] for i in range(n + 1)]
uf_p = UnionFind(n + 1)
uf_m = UnionFind(n + 1)
for a, b in ab:
    uf_p.union(a, b)
    graph[a].append(b)
    graph[b].append(a)
for c, d in cd:
    if uf_p.same(c, d):
        uf_m.union(c, d)
ans = [0] * n
for i in range(1, n + 1):
    ans[i - 1] = max(uf_p.size(i) - uf_m.size(i) - len(graph[i]), 0)
print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


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, readline().split())
ab = [list(map(int, readline().split())) for _ in range(m)]
cd = [list(map(int, readline().split())) for _ in range(k)]
graph = [[] for i in range(n + 1)]
uf_p = UnionFind(n + 1)
uf_m = UnionFind(n + 1)
for a, b in ab:
    uf_p.union(a, b)
    graph[a].append(b)
    graph[b].append(a)
for c, d in cd:
    if uf_p.same(c, d):
        uf_m.union(c, d)
ans = [0] * n
for i in range(1, n + 1):
    ans[i - 1] = uf_p.size(i) - uf_m.size(i) - len(graph[i])
print(*ans)

Submission status: Wrong Answer

Solution code:
n,m,k = map(int,input().split())
relfr = {i:set() for i in range(n)}
relbl = {i:set() for i in range(n)}
for i in range(m):
    a,b = map(int,input().split())
    relfr[a-1].add(b-1)
    relfr[b-1].add(a-1)
for i in range(k):
    a,b = map(int,input().split())
    relbl[a-1].add(b-1)
    relbl[b-1].add(a-1)
blsiz = [0 for i in range(n)]
ans = [0]*n

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    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):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return
        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
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
      
uf = UnionFind(n)
for i in range(n):
    for j in relfr[i]:
        uf.Unite(i,j)
for i in range(n):
    for j in relbl[i]:
        uf.Unite(i,j)
        
for i in range(n):
    ans[i]=uf.Count(i)-len(relfr[i])-len(relbl[i])-1
 
print(' '.join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
from collections import Counter
n, m, k = map(int, input().split())
fr = [sorted(list(map(int, input().split()))) for _ in range(m)]
bl = [sorted(list(map(int, input().split()))) for _ in range(k)]
ren = [0] * (n + 1)
tomon = [0] * (n + 1)
blon = [0] * (n + 1)
deta = 0
for i in range(m):
    tomon[fr[i][0]] += 1
    tomon[fr[i][1]] += 1
    if ren[fr[i][0]] != 0:
        if ren[fr[i][1]] != 0:
            continue
        else:
            ren[fr[i][1]] = ren[fr[i][0]]
    else:
        deta += 1
        ren[fr[i][0]] = deta
        ren[fr[i][1]] = deta
        
dic = Counter(ren)

for i in range(k):
    if ren[bl[i][0]] == ren[bl[i][1]]:
        blon[bl[i][0]] += 1
        blon[bl[i][1]] += 1
for i in range(1,n):
    print(dic[ren[i]] - tomon[i] - blon[i] - 1, end = " ")
print(dic[ren[n]] - tomon[n] - blon[n] - 1)

Submission status: Wrong Answer

Solution code:
N, M, K = map(int, input().split())
ans = [0] * (N + 1)
child = {i:[] for i in range(1, N+1)}
isChecked = [0] * (N + 1)
isBlocked = [set() for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    child[a].append(b)
    child[b].append(a)
    
for _ in range(K):
    c, d = map(int, input().split())
    isBlocked[c].add(d)
    isBlocked[d].add(c)
    
for i in range(1, N+1):
    if isChecked[i]:
        continue
    isChecked[i] = 1
    x = set([i])
    ch = child[i].copy()
    while ch:
        c = ch.pop()
        if isChecked[c]:
            continue
        isChecked[c] = 1
        x.add(c)
        ch.extend(child[c])
    print(x)
    for j in x:
        ans[j] = len(x) - 1 - len(child[j]) - len(x & isBlocked[j])
        
print(*ans[1:])

Submission status: Wrong Answer

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

    def find(self, x):#要素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が属するグループと要素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):#要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):#要素x, yが同じグループに属するかどうかを返す

        return self.find(x) == self.find(y)

    def members(self, x):#要素xが属するグループに属する要素をリストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def 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):#all_group_members O(N)かかるので注意
        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())

uff=UnionFind(n+1)
ab=[]
cd=[]
for i in range(m):
    ab.append(list(map(int,input().split())))

for i in range(k):
    cd.append(list(map(int,input().split())))


adlist_ab=[ [i+1] for i in range(n)]#交流のあるやつ同士の隣接リスト
for i in range(m):#1から順に見ていく
    x=ab[i][0]
    y=ab[i][1]
    adlist_ab[x-1].append(y)
    adlist_ab[y-1].append(x)

for i in range(m):
   # print("gn")
    a=ab[i][0]
    b=ab[i][1]
    if uff.same(a,b)==False:
        uff.union(a,b)
friend=[]
block=[]
for i in range(1,n+1):
    friend.append(uff.size(i))

ufb=UnionFind(n+1)

for i in range(k):
   # print("gn")
    a=cd[i][0]
    b=cd[i][1]
    if uff.same(a,b)==True:
        ufb.union(a,b)

for i in range(1,n+1):
    block.append(ufb.size(i)-1)
#print(friend)
#print(block)

#for i in range(n):
#    print(len(adlist_ab[i]),end=" ")
#print()


for i in range(n):
    print(friend[i]-block[i]-len(adlist_ab[i]),end=" ")

Submission status: Wrong Answer

Solution code:
N, M, K = map(int, input().split())
ans = [0] * (N + 1)
child = {i:[] for i in range(1, N+1)}
group_id = {i:[] for i in range(1, N+1)}
group = {}
isChecked = [0] * (N + 1)

for _ in range(M):
    a, b = map(int, input().split())
    child[a].append(b)
    child[b].append(a)
    
X = []
g = 0
i = 1
while len(X) != N:
    if isChecked[i]:
        i += 1
        continue
    isChecked[i] = 1
    group_id[i] = g
    x = [i]
    ch = child[i].copy()
    while ch:
        print(ch)
        c = ch.pop(0)
        group_id[c] = g
        isChecked[c] = 1
        for j in child[c]:
            if not isChecked[j] and j not in ch:
                ch.append(j)
        x.append(c)
    group[g] = len(x)
    X += x
    if g % 1000 == 0:
        print(g)
    g += 1
    i += 1

for i in range(1, N+1):
    ans[i] = group[group_id[i]] - len(child[i]) - 1

for _ in range(K):
    c, d = map(int, input().split())
    if group_id[c] == group_id[d]:
        ans[c] -= 1
        ans[d] -= 1
        
print(*ans[1:])

Submission status: Wrong Answer

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

    def find(self, x):#要素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が属するグループと要素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):#要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):#要素x, yが同じグループに属するかどうかを返す

        return self.find(x) == self.find(y)

    def members(self, x):#要素xが属するグループに属する要素をリストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def 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):#all_group_members O(N)かかるので注意
        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())

uff=UnionFind(n+1)
ab=[]
cd=[]
for i in range(m):
    ab.append(list(map(int,input().split())))

for i in range(k):
    cd.append(list(map(int,input().split())))


adlist_ab=[ [i+1] for i in range(n)]#交流のあるやつ同士の隣接リスト
for i in range(m):#1から順に見ていく
    x=ab[i][0]
    y=ab[i][1]
    adlist_ab[x-1].append(y)
    adlist_ab[y-1].append(x)

for i in range(m):
   # print("gn")
    a=ab[i][0]
    b=ab[i][1]
    if uff.same(a,b)==False:
        uff.union(a,b)
friend=[]
block=[]
for i in range(1,n+1):
    friend.append(uff.size(i))

ufb=UnionFind(n+1)

for i in range(k):
   # print("gn")
    a=cd[i][0]
    b=cd[i][1]
    if ufb.same(a,b)==False:
        ufb.union(a,b)

for i in range(1,n+1):
    block.append(ufb.size(i)-1)
#print(friend)
#print(block)

#for i in range(n):
#    print(len(adlist_ab[i]),end=" ")
#print()


for i in range(n):
    print(friend[i]-block[i]-len(adlist_ab[i]),end=" ")

Submission status: Wrong Answer

Solution code:
n,m,k=map(int,input().split())
fr=[input() for i in range(m)]
bl=[input() for i in range(k)]
rel=[[0]*n for i in range(n)]
for i in range(n):
  rel[i][i]=''
relmap=[0]*n
for l in fr:
  a,b=map(int,l.split())
  rel[a-1][b-1]+=1
  rel[b-1][a-1]+=1
for l in bl:
  a,b=map(int,l.split())
  rel[a-1][b-1]-=1
  rel[b-1][a-1]-=1
#for i in range(n):
#print(rel)

Submission status: Wrong Answer

Solution code:
nmk_list = input().split(" ")
N = int(nmk_list[0])
M = int(nmk_list[1])
K = int(nmk_list[2])

n_list =[[0 for j in range(N)] for i in range(N)]

for m in range(M):
    ab = input().split(" ")
    a = int(ab[0])-1
    b = int(ab[1])-1
    n_list[a][b] = 1
    n_list[b][a] = 1
for k in range(K):
    cd = input().split(" ")
    c = int(cd[0])-1
    d = int(cd[1])-1
    n_list[c][d] = -1
    n_list[d][c] = -1

graph_group = [-1 for i in range(N)]
group_no = 0
dict = {}
for i in range(N):
    if graph_group[i] == -1:
        queue = [i]
        visit = [0 for num in range(N)]
        visit[i] = 1
        graph_group[i] = group_no
        q = 0
        while True:
            pop = queue[q]
            for j in range(N):
                if n_list[pop][j] == 1 and visit[j] == 0:
                    queue.append(j)
                    visit[j] = 1
                    graph_group[j] = group_no
            q += 1
            if len(queue) == q:
                break
        dict[group_no] = queue
        frbl_sum = 0
        for j in queue:
            if n_list[i][j] != 0:
                frbl_sum += 1
        print(q-frbl_sum-1,end = " ")
        group_no += 1
    else:
        group_no = graph_group[i]
        q = graph_group.count(group_no)
        queue = dict[group_no]
        frbl_sum = 0
        for j in queue:
            if n_list[i][j] !=0:
                frbl_sum += 1
        print(q-frbl_sum-1,end = " ")

Submission status: Wrong Answer

Solution code:
#n:
#m:
#k:
n,m,k=map(int,input().split())
friend={}
block={}
result=[]
for i in range(1,n+1):
    friend[i]=set([])
    block[i]=set([])
    result.append(0)

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

for _ in range(k):
    a,b=map(int,input().split())
    block[a].add(b)
    block[b].add(a)


checked=set([])
bfbf=[]
for i in range(1,n+1):
    #print(i,checked)
    if i not in checked:
        checked.add(i)
        group=set([i])
        bf=set([i])
        while len(group)!= 0:
            temp=group.pop()
            for item in friend[temp]:
                if item not in checked:
                    checked.add(item)
                    group.add(item)
                    bf.add(item)
        lenbf=len(bf)
        for item1 in bf:
            bl=0
            result[item1-1]=lenbf-1-len(list(friend[item1]))-bl



        bfbf.append(bf)
result=list(map(str,result))
print(" ".join(result))

Submission status: Wrong Answer

Solution code:
class UnionFind():

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

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

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        if self.parents[x] > self.parents[y]:
            rx, ry = ry, rx
        self.parents[rx] += self.parents[ry]
        self.parents[ry] = rx

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

    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry


n, m, k = map(int, input().split())
friend_cand = UnionFind(n)
friend_cnt = {}
for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    friend_cnt[a] = friend_cnt.get(a, 0) + 1
    friend_cnt[b] = friend_cnt.get(b, 0) + 1
    friend_cand.unite(a, b)

block_cnt = {}
for _ in range(k):
    c, d = map(lambda x: int(x)-1, input().split())
    block_cnt[c] = block_cnt.get(c, 0) + 1
    block_cnt[d] = block_cnt.get(d, 0) + 1

for i in range(n-1):
    print(friend_cand.size(i)-friend_cnt.get(i, 0)-block_cnt.get(i, 0)-1, end=' ')
print(friend_cand.size(i+1)-friend_cnt.get(i+1, 0)-block_cnt.get(i+1, 0)-1)