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 time
#start = time.time()

# スペース区切りの整数入力
N,M,K = map(int, input().split())

fcnum = [ 0 for i in range(N+1)]
fring = [[] for i in range(N+1)]
frno =  [-1 for i in range(N+1)]

ab = []
for i in range(M):
    aa,bb = map(int, input().split())
    if aa > bb:
        aa,bb = bb,aa
    fcnum[aa] -= 1
    fcnum[bb] -= 1
    ab.append([aa,bb])

for aa,bb in ab:
    if frno[aa] == -1 and frno[bb] == -1:
        frn = aa
        frno[aa] = frn
        frno[bb] = frn
        fring[frn].append(aa)
        fring[frn].append(bb)
    elif frno[aa] == -1 and frno[bb] != -1:
        frn = frno[bb]
        frno[aa] = frn
        fring[frn].append(aa)
    elif frno[aa] != -1 and frno[bb] == -1:
        frn = frno[aa]
        frno[bb] = frn
        fring[frn].append(bb)
    else:
        if frno[aa] != frno[bb]:
            if len(fring[frno[aa]]) > len(fring[frno[bb]]):
                frnto = frno[aa]
                frnfrom = frno[bb]
            else:
                frnto = frno[bb]
                frnfrom = frno[aa]
            fring[frnto].extend(fring[frnfrom])
            for mvf in fring[frnfrom]:
                frno[mvf] = frnto
            fring[frnfrom] = []

for i in range(K):
    cc,dd = map(int, input().split())
    if frno[cc] == frno[dd]:
        fcnum[cc] -= 1
        fcnum[dd] -= 1

for k in range(1,len(fring)):
    cnum = len(fring[k]) - 1
    for ff in fring[k]:
        fcnum[ff] += cnum

for i in range(1,len(fcnum)):
    print(fcnum[i]," ",end="")

Submission status: Wrong Answer

Solution code:
#import time
#start = time.time()

# スペース区切りの整数入力
N,M,K = map(int, input().split())

fcnum = [ 0 for i in range(N+1)]
fring = [[] for i in range(N+1)]
frno =  [-1 for i in range(N+1)]

ab = []
for i in range(M):
    aa,bb = map(int, input().split())
    if aa > bb:
        aa,bb = bb,aa
    fcnum[aa] -= 1
    fcnum[bb] -= 1
    ab.append([aa,bb])

for i in range(K):
    cc,dd = map(int, input().split())
    if frno[cc] == frno[dd]:
        fcnum[cc] -= 1
        fcnum[dd] -= 1

for aa,bb in ab:
    if frno[aa] == -1 and frno[bb] == -1:
        frn = aa
        frno[aa] = frn
        frno[bb] = frn
        fring[frn].append(aa)
        fring[frn].append(bb)
    elif frno[aa] == -1 and frno[bb] != -1:
        frn = frno[bb]
        frno[aa] = frn
        fring[frn].append(aa)
    elif frno[aa] != -1 and frno[bb] == -1:
        frn = frno[aa]
        frno[bb] = frn
        fring[frn].append(bb)
    else:
        if frno[aa] != frno[bb]:
            if len(fring[frno[aa]]) > len(fring[frno[bb]]):
                frnto = frno[aa]
                frnfrom = frno[bb]
            else:
                frnto = frno[bb]
                frnfrom = frno[aa]
            fring[frnto].extend(fring[frnfrom])
            for mvf in fring[frnfrom]:
                frno[mvf] = frnto
            fring[frnfrom] = []

for k in range(1,len(fring)):
    cnum = len(fring[k]) - 1
    for ff in fring[k]:
        fcnum[ff] += cnum

for i in range(1,len(fcnum)):
    print(fcnum[i]," ",end="")

Submission status: Wrong Answer

Solution code:
n,m,k=map(int,input().split())
a=[list(map(int,input().split())) for i in range(m)]
c=[list(map(int,input().split())) for i in range(k)]

lf=[[] for i in range(n)]
for i in range(m):
    lf[a[i][0]-1].append(a[i][1])
    lf[a[i][1]-1].append(a[i][0])
lb=[[] for i in range(n)]
for i in range(k):
    lb[c[i][0]-1].append(c[i][1])
    lb[c[i][1]-1].append(c[i][0])

lc=[[] for i in range(n)]
for i in range(m):
    lc[a[i][0]-1].append(a[i][1])
    lc[a[i][1]-1].append(a[i][0])

ll=[]
for i in range(n):
    if i not in ll:
        l=set(lc[i])
        for j in lc[i]:
            for p in lf[j-1]:
                if p not in l:
                    lc[i].append(p)
                    l.add(p)
        for j in l:
            lc[j-1]=lc[i]
            ll.append(j-1)

lm=[]
for i in range(n):
    lm.append(len(lc[i])-len(lf[i])-1)
    for j in lb[i]:
        if j in lc[i]:
            lm[i]-=1

for i in lm:
    print(i,end=" ")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N, M, K = map(int, input().split())
F = [tuple(map(lambda s: int(s) - 1, input().split())) for i in range(M)]
B = [tuple(map(lambda s: int(s) - 1, input().split())) for i in range(K)]


class DisjointSet():
    def __init__(self, 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 unite(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.d[x] == self.d[y]

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


d = DisjointSet(N)
friends = defaultdict(int)
for Ai, Bi in F:
    d.unite(Ai, Bi)
    friends[Ai] += 1
    friends[Bi] += 1
blocking = defaultdict(list)
for Ci, Di in B:
    blocking[Ci].append(Di)
    blocking[Di].append(Ci)

ans = [0] * N
for i in range(N):
    ans[i] = d.size(i) - friends[i] - 1
    for b in blocking[i]:
        if d.same(i, b):
            ans[i] -= 1
print(' '.join(list(map(str, ans))))

Submission status: Wrong Answer

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

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

def root(x):
    global parent
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    global parent
    global sizes
    x = root(x)
    y = root(y)
    if x == y:
        return
    # parent[x] = y
    # sizes[x] = sizes[x] + sizes[y]
    # sizes[y] = sizes[x]

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

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

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

for i in range(n):
    x = root(i)
    s = sizes[x]
    candidates[i] = s - len(friends[i]) - len(blocks[i]) - 1

print(*candidates)

Submission status: Wrong Answer

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

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

def root(x):
    global parent
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    global parent
    global sizes
    x = root(x)
    y = root(y)
    if x == y:
        return
    parent[x] = y
    sizes[x] = sizes[x] + sizes[y]
    sizes[y] = sizes[x]

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

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

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

for i in range(n):
    x = root(i)
    s = sizes[x]
    candidates[i] = s - len(friends[i]) - len(blocks[i]) - 1

print(*candidates)

Submission status: Wrong Answer

Solution code:
class Unionfind:

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

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

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

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

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

n,m,k = map(int,input().split())
un = Unionfind(n)
fre = [1]*n
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    un.union(a,b)
    fre[a] += 1

ans = [un.size(i)-fre[i] for i in range(n)]

for i in range(k):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    if un.same(a,b):
        ans[a] -= 1
        ans[b] -= 1
print(*ans)

Submission status: Wrong Answer

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

Frends = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a < b:
        Frends[a].append(b)
    else:
        Frends[b].append(a)

Blocked = [[] for _ in range(N)]
for _ in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if c < d:
        Blocked[c].append(d)
    else:
        Blocked[d].append(c)

# process
# 友人グループを作成
fg = []
for i in range (N):
    fs = Frends[i]
    for f in fs:
        flg = False
        t = set()
        for g in fg:
            if i in g and f in g:
                if len(t) == 0:
                    flg = True
                    t = g                 
                else:
                    t = t | g
                    fg.remove(g)
            elif not (i in g or f in g):
                continue
            else:
                if len(t) == 0:
                    if i in g:
                        g.add(f)
                    else:
                        g.add(i)
                
                    flg = True
                    t = g
                else:
                    t = t | g
                    fg.remove(g)

        if not flg:
            fg.append(set([i, f]))

#print(fg)

# 友人候補を抽出
cand = []
for i in range(N):
    for g in fg:
        if i in g:
            for f in g:
                if i < f and not f in Frends[i] and not f in Blocked[i]:
                    cand.append((i, f,))

# 友人候補をカウント
ans = [0 for _ in range(N)]
for c in cand:
    a, b = c
    ans[a] += 1
    ans[b] += 1

# output
print(" ".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left,bisect_right,insort
input = sys.stdin.readline

def main():
    #根を探す。
    #別なグループ間をつなげた場合は、つなげた先の根に書き換える。
    def find(x):
        if d[x]<0:
            return x
        else:
            d[x]=find(d[x])
            return d[x]

    #二つのグループをつなげる
    #大きいほうに小さいほうをつなげる。
    def unite(x,y):
        x=find(x)
        y=find(y)
        if x==y:
            return False
        if d[x]>d[y]:
            c=x
            x=y
            y=c
        d[x]+=d[y]
        d[y]=x
        return True

    #根が同じかどうか判定
    def same(x,y):
        return find(x)==find(y)

    #サイズを取得（根に入っている数値=サイズの負値）
    def size(x):
        return -d[find(d[x])]

    n,m,k=map(int,input().split())
    d=[-1]*(n+1)
    ans=[0]*(n+1)
    for i in range(m):
        a,b=map(int,input().split())
        ans[a]-=1
        ans[b]-=1
        unite(a,b)
    for i in range(k):
        a,b=map(int,input().split())
        if same(a,b):
            ans[a]-=1
            ans[b]-=1
    for i in range(1,n+1):
        ans[i]+=size(i)-1
    print(" ".join(map(str,ans[1:])))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,M,K = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(M)]
CD = [list(map(int, input().split())) for i in range(K)]

frends = [set() for i in range(N)]
not_frends_koho = [set() for i in range(N)]
frends_koho = []
people = set(range(N))

for relF in AB:
    frends[relF[0]-1].add(relF[1]-1)
    frends[relF[1]-1].add(relF[0]-1)

for relF in AB:
    not_frends_koho[relF[0]-1].add(relF[1]-1)
    not_frends_koho[relF[1]-1].add(relF[0]-1)

for relB in CD:
    not_frends_koho[relB[0]-1].add(relB[1]-1)
    not_frends_koho[relB[1]-1].add(relB[0]-1)
  
for i in range(len(not_frends_koho)):
    frends_koho.append((people - not_frends_koho[i]) - set([i]))
    
memo = []

def search(idx, goal, memo_str):
    if str(goal) in memo_str and memo_str not in memo and memo_str[-1] == str(goal):
        memo.append(memo_str)
        return
    
    if str(idx) in memo_str:
        return
    
    memo_str += str(idx)
    
    for num in frends[idx]:
        search(num, goal, memo_str)


for start in range(len(frends_koho)):
    if frends_koho[start]:
        for end in frends_koho[start]:
            search(start, end, '')

memo = set([num[0] + num[-1] for num in memo])

ans = [0 for i in range(N)]
for i in memo:
    ans[int(i[0])] += 1

for i in ans:print(i, end=' ')

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left,bisect_right,insort
input = sys.stdin.readline

def main():
    #根を探す。
    #別なグループ間をつなげた場合は、つなげた先の根に書き換える。
    def find(x):
        if d[x]<0:
            return x
        else:
            d[x]=find(d[x])
            return d[x]

    #二つのグループをつなげる
    #大きいほうに小さいほうをつなげる。
    def unite(x,y):
        x=find(x)
        y=find(y)
        if x==y:
            return False
        if d[x]>d[y]:
            c=x
            x=y
            y=c
        d[x]+=d[y]
        d[y]=x
        return True

    #根が同じかどうか判定
    def same(x,y):
        return find(x)==find(y)

    #サイズを取得（根に入っている数値=サイズの負値）
    def size(x):
        return -d[find(d[x])]

    n,m,k=map(int,input().split())
    d=[-1]*(n+1)
    fl=[0]*(n+1)
    bl=[[] for _ in range(n+1)]
    ans=[0]*(n+1)
    for i in range(m):
        a,b=map(int,input().split())
        fl[a]+=1
        fl[b]+=1
        unite(a,b)
    for i in range(k):
        a,b=map(int,input().split())
        bl[a].append(b)
        bl[b].append(a)
    for i in range(1,n+1):
        ans[i]=size(i)-1-fl[i]
        for j in bl[i]:
            if same(j,i):
                ans[i]-=1
    print(" ".join(map(str,ans[1:])))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
class UnionFind:
    def __init__(self, n=0):
        self.d = [-1 for _ in range(n)]
    
    def find(self, x): # find root
        if self.d[x] < 0: return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return False
        if -self.d[x] < -self.d[y]: # swap
            t = x
            x = y
            y = t
        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)]
    

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

    deg = [0 for _ in range(N)]
    for _ in range(M): # friends
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        deg[a] += 1
        deg[b] += 1
        uf.unite(a, b)
    print('----')
    print(uf.d)


    to = [[] for _ in range(N)]
    for _ in range(K): # block
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        to[c].append(c)
        to[d].append(d)

    ret = []
    for i in range(N):
        ans = uf.size(i) - 1 - deg[i]
        for u in to[i]:
            if uf.same(i, u): ans -= 1
        ret.append(str(ans))

    print(' '.join(ret))


main()

Submission status: Wrong Answer

Solution code:
n,m,k=map(int,input().split())
a=[list(map(int,input().split())) for i in range(m)]
c=[list(map(int,input().split())) for i in range(k)]

lf=[[] for i in range(n)]
for i in range(m):
    lf[a[i][0]-1].append(a[i][1])
    lf[a[i][1]-1].append(a[i][0])
lb=[[]for i in range(n)]
for i in range(k):
    lb[c[i][0]-1].append(c[i][1])
    lb[c[i][1]-1].append(c[i][0])

lc=[[] for i in range(n)]
for i in range(m):
    lc[a[i][0]-1].append(a[i][1])
    lc[a[i][1]-1].append(a[i][0])

ll=[]
for i in range(n):
    if i not in ll:
        l=set(lc[i])
        for j in lc[i]:
            for p in lf[j-1]:
                if p not in l:
                    lc[i].append(p)
                    l.add(p)
        lc[i]=l
        for j in l:
            lc[j-1]=l
            ll.append(j-1)
        


lm=[]
for i in range(n):
    lm.append(len(lc[i])-len(lf[i])-1)
    for j in lb[i]:
        if j in lc[i]:
            lm[i]-=1

for i in lm:
    print(i,end=" ")

Submission status: Wrong Answer

Solution code:
n, m, k = map(int, input().split())
friend = [{i+1} for i in range(n)]
exclude = [set() for _ in range(n)]
for _ in range(m):
	a,b = map(int, input().split())
	exclude[a-1].add(b)
	exclude[b-1].add(a)
	ai = bi = -1
	for i, f in enumerate(friend):
		if a in f:
			ai = i
		if b in f:
			bi = i
	if ai != bi and ai != -1 and bi != -1:
		friend[ai] = friend[ai] | friend[bi]
		friend.pop(bi)
	elif ai != -1:
		friend[ai].add(b)
	elif bi != -1:
		friend[bi].add(a)
	else:
		friend.append({a,b})
for _ in range(k):
	c,d = map(int, input().split())
	exclude[c-1].add(d)
	exclude[d-1].add(c)
# print(friend)
# print(exclude)

ans = ""
for f in friend:
	for ff in f:
		ans += str(len(f - exclude[ff-1]) - 1) + " "

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

Submission status: Wrong Answer

Solution code:
import numpy as np
N,M,K = map(int,input().split())
answer_list = [0]*N
frend_list = [[0] * N for i in range(N)]
flag_list = [0]*N
for i in range(M):
    num_list= list(map(int,input().split()))
    frend_list[num_list[0]-1][num_list[1]-1] = 1
    frend_list[num_list[1]-1][num_list[0]-1] = 1

for i in range(K):
    num_list= list(map(int,input().split()))
    frend_list[num_list[0]-1][num_list[1]-1] = 3
    frend_list[num_list[1]-1][num_list[0]-1] = 3
    
    
for i in range(len(answer_list)):
    for n in range(len(frend_list[i])):
        if (frend_list[i][n] == 0) & (i != n):
            flag_list = (np.array(frend_list[n])+np.array(frend_list[i]))
            flag_list = flag_list.tolist()
            for g in flag_list:
                if g == 2:
                    answer_list[i] += 1
print(*answer_list)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
N, M, K = map(int, input().split())
graph = [[] for _ in range(N)]
block = [[] for _ in range(N)]
connected_components = []
count = 0
counts = [0 for _ in range(N)]
seen = [False for _ in range(N)]
def dfs(v, c, seen, origin):
    global count
    seen[v] = True
    for node in graph[v]:
        if seen[node] == True:
            continue
        if node not in block[origin]:
            count += 1
        dfs(node, c+1, seen, origin)
def dfs_connected(v, order):
    seen[v] = True

Submission status: Wrong Answer

Solution code:
n, m, k = map(int, input().split())
friend = [{i+1} for i in range(n)]
exclude = [set() for _ in range(n)]
# print(exclude)
for _ in range(m):
	a,b = map(int, input().split())
	exclude[a-1].add(b)
	exclude[b-1].add(a)
	ai, bi = -1 , -1
	for i, f in enumerate(friend):
		if a in f:
			ai = i
		if b in f:
			bi = i
	if ai != bi and ai != -1 and bi != -1:
		friend[ai] = friend[ai] | friend[bi]
		friend.pop(bi)
	elif ai != -1:
		friend[ai].add(b)
	elif bi != -1:
		friend[bi].add(a)
	else:
		friend.append({a,b})
for _ in range(k):
	c,d = map(int, input().split())
	exclude[c-1].add(d)
	exclude[d-1].add(c)
# print(friend)
# print(exclude)

ans = [[] for _ in range(n)]
for f in friend:
	for ff in f:
		ans[ff-1] = str(len(f) - len(exclude[ff-1]) - 1)

print(" ".join(ans))

Submission status: Wrong Answer

Solution code:
n, m, k = map(int, input().split())
friend = [{i+1} for i in range(n)]
exclude = [set() for _ in range(n)]
print(exclude)
for _ in range(m):
	a,b = map(int, input().split())
	exclude[a-1].add(b)
	exclude[b-1].add(a)
	ai, bi = -1 , -1
	for i, f in enumerate(friend):
		if a in f:
			ai = i
		if b in f:
			bi = i
	if ai != bi and ai != -1 and bi != -1:
		friend[ai] = friend[ai] | friend[bi]
		friend.pop(bi)
	elif ai != -1:
		friend[ai].add(b)
	elif bi != -1:
		friend[bi].add(a)
	else:
		friend.append({a,b})
for _ in range(k):
	c,d = map(int, input().split())
	exclude[c-1].add(d)
	exclude[d-1].add(c)
# print(friend)
# print(exclude)

ans = [[] for _ in range(n)]
for f in friend:
	for ff in f:
		ans[ff-1] = str(len(f - exclude[ff-1]) - 1)

print(" ".join(ans))

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""
import collections
import itertools
import operator


class UnionFind:
    def __init__(self, x):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)
        self.size = collections.defaultdict(lambda: 1)
        if x is not None:
            for elem in range(x+1):
                _, _, _ = self.parent[elem], self.rank[elem],self.size[elem]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if not self.are_same(x,y):
            xx = self.size[x]
            yy = self.size[y]
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += xx
            else:
                self.parent[y] = x
                self.size[x] += yy
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

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

    def are_same(self, x, y):
        '''print(x,y,self.find(x),self.find(y),self.find(x) == self.find(y))'''
        return self.find(x) == self.find(y)

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield set(x for x, _ in group)

N,M,K = m()

po = [0 for i in range(N)]

uni = UnionFind(N-1)
unii = UnionFind(N-1)

for i in range(M):
    x,y = m()
    po[x-1] -= 1
    po[y-1] -= 1
    uni.unite(x-1,y-1)

for i in range(K):
    x,y = m()
    unii.unite(x-1,y-1)

a = list(uni.grouper())
b = list(unii.grouper())

for i in range(len(a)):
    for popo in a[i]:
        for j in range(len(b)):
            if popo in b[j]: 
                
                po[popo] += len(a[i]) - len(a[i] & b[j])
                break
print(jo(po))

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""
import collections
import itertools
import operator


class UnionFind:
    def __init__(self, x):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)
        self.size = collections.defaultdict(lambda: 1)
        if x is not None:
            for elem in range(x+1):
                _, _, _ = self.parent[elem], self.rank[elem],self.size[elem]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if not self.are_same(x,y):
            xx = self.size[x]
            yy = self.size[y]
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += xx
            else:
                self.parent[y] = x
                self.size[x] += yy
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

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

    def are_same(self, x, y):
        '''print(x,y,self.find(x),self.find(y),self.find(x) == self.find(y))'''
        return self.find(x) == self.find(y)

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield set(x for x, _ in group)

N,M,K = m()

po = [0 for i in range(N)]

uni = UnionFind(N-1)
unii = UnionFind(N-1)

for i in range(M):
    x,y = m()
    po[x-1] -= 1
    po[y-1] -= 1
    uni.unite(x-1,y-1)

for i in range(K):
    x,y = m()
    unii.unite(x-1,y-1)

a = list(uni.grouper())
b = list(unii.grouper())

for i in range(len(a)):
    for popo in a[i]:
        for j in range(len(b)):
            if popo in b[j]: 
                print(popo,a[i] & b[j])
                po[popo] += len(a[i]) - len(a[i] & b[j])
                break
print(jo(po))

Submission status: Wrong Answer

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

relations=[[None for i in range(n)]for i in range(n)]
option=[]

for i in range(m):
    x,y=map(int,input().split())
    if i==0:
        option.append(x-1)
    relations[x-1][y-1]=True
    relations[y-1][x-1]=True
for i in range(k):
    x,y=map(int,input().split())
    relations[x-1][y-1]=False
    relations[y-1][x-1]=False

completed=[False for i in range(n)]
groups=[]
group=[]

while option:
    now=option.pop()
    group.append(now)
    completed[now]=True
    for target,relation in enumerate(relations[now]):
        if relation==True and completed[target]==False and target not in option:
            option.append(target)

    if len(option)==0:
        groups.append(set(group))
        group=[]
        for i in range(n):
            if completed[i]==False:
                option.append(i)
                break

Submission status: Wrong Answer

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

relations=[[None for i in range(n)]for i in range(n)]
option=[]

for i in range(m):
    x,y=map(int,input().split())
    if i==0:
        option.append(x-1)
    relations[x-1][y-1]=True
    relations[y-1][x-1]=True
for i in range(k):
    x,y=map(int,input().split())
    relations[x-1][y-1]=False
    relations[y-1][x-1]=False

completed=[False for i in range(n)]
groups=[]
group=[]

while option:
    now=option.pop()
    group.append(now)
    completed[now]=True
    for target,relation in enumerate(relations[now]):
        if relation==True and completed[target]==False and target not in option:
            option.append(target)

    if len(option)==0:
        groups.append(set(group))
        group=[]
        for i in range(n):
            if completed[i]==False:
                option.append(i)
                break

for i in range(n):
    for group in groups:
        if i in group:
            cnt=0
            for x,relation in enumerate(relations[i]):
                if relation!=None and x in group:
                    cnt+=1
            print(len(group)-cnt-1,end=" ")