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: Runtime Error

Solution code:
N,M,K=map(int,input().split())
par=[i for i in range(N)]
siz=[1 for _ in range(N)]

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

def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        par[a]=b
        siz[b]+=siz[a]

def size(a):
    return siz[find(a)]

def same(a,b):
    return find(a)==find(b)

ans=[0 for i in range(N)]
for _ in range(M):
    A,B=map(int,input().split())
    A,B=A-1,B-1
    union(A,B)
    ans[A]-=1
    ans[B]-=1
for i in range(N):
    ans[i]+=size(i)-1
for _ in range(K):
    C,D=map(int,input().split())
    C,D=C-1,D-1
    if(same(C,D)):
        ans[C]-=1
        ans[D]-=1
        
print(*ans)

Submission status: Runtime Error

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

f = [[] for i in range(N)]
fc = [[] for i in range(N)]

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

def make_fc(p, n):
	for i in f[n]:
		if i in fc[p]:
			continue
		fc[p].append(i)
		make_fc(p, i)

for i in range(N):
	make_fc(i, i)

for i in range(N):
	for j in f[i]:
		if j in fc[i]:
			fc[i].remove(j)

for i in range(K):
	c, d = map(int, input().split())
	c -= 1
	d -= 1
	if d in fc[c]:
		fc[c].remove(d)
	if c in fc[d]:
		fc[d].remove(c)

for i in range(N):
	fc[i].remove(i)

for i in range(N):
	print(len(fc[i]), end = "")
	print(" ", end = "")

print()

Submission status: Runtime Error

Solution code:
N,M,K=map(int,input().split())
par=[i for i in range(N)]
siz=[1 for i in range(N)]
fri=[0 for i in range(N)]
blo=[0 for i in range(N)]

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

def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        par[a]=b
        siz[b]+=siz[a]

def size(a):
    return siz[find(a)]

def same(a,b):
    return find(a)==find(b)

ans=[0 for i in range(N)]
for i in range(M):
    A,B=map(int,input().split())
    A,B=A-1,B-1
    union(A,B)
    ans[A]-=1
    ans[B]-=1
for i in range(N):
    ans[i]+=size(i)-1
for i in range(K):
    C,D=map(int,input().split())
    C,D=C-1,D-1
    if(same(C,D)):
        ans[C]-=1
        ans[D]-=1
        
print(*ans)

Submission status: Runtime Error

Solution code:
N,M,K=map(int,input().split())
par=[i for i in range(N)]
siz=[1 for i in range(N)]
fri=[0 for i in range(N)]
blo=[0 for i in range(N)]
rank=[0 for i in range(N)]

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

def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        par[a]=b
        siz[b]+=siz[a]

def size(a):
    return siz[find(a)]

def same(a,b):
    return find(a)==find(b)

for i in range(M):
    A,B=map(int,input().split())
    A,B=A-1,B-1
    union(A,B)
    fri[A]+=1
    fri[B]+=1
for i in range(K):
    C,D=map(int,input().split())
    C,D=C-1,D-1
    if(same(C,D)):
        blo[C]+=1
        blo[D]+=1

ans=[size(i)-fri[i]-blo[i]-1 for i in range(N)]
print(*ans)

Submission status: Runtime Error

Solution code:
N,M,K=map(int,input().split())
par=[i for i in range(N+10)]
siz=[1 for i in range(N+10)]
fre=[0 for i in range(N+10)]
blo=[0 for i in range(N+10)]
rank=[0 for i in range(N+10)]

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

#木をつなぐ
def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        par[a]=b
        siz[b]+=siz[a]

def size(a):
    return siz[find(a)]

def same(a,b):
    return find(a)==find(b)

for i in range(M):
    A,B=map(int,input().split())
    union(A,B)
    fre[A]+=1
    fre[B]+=1
for i in range(K):
    C,D=map(int,input().split())
    if(same(C,D)):
        blo[C]+=1
        blo[D]+=1

for i in range(1,N+1):
    print(size(i)-fre[i]-blo[i]-1,end=' ')

Submission status: Runtime Error

Solution code:
    import sys
    sys.setrecursionlimit(5000)
     
    N,M,K = list(map(int,input().split(' ')))
     
    friend_list = [0]*(N+1)
    bad_list = [0]*(N+1)
    group = {}
     
    parent = [i for i in range(N+1)]
     
    def union(x,y):
        x = find(x)
        y = find(y)
        parent[x] = y
     
    def find(x):
        if parent[x] == x:
            return x
        else:
            parent[x]= find(parent[x])
            return parent[x]
     
     
     
    for i in range(M):
        A,B = list(map(int,input().split(' ')))
        friend_list[A]+=1
        friend_list[B]+=1
        
        union(A,B)
     
    for i in range(1,N+1):
        oya = find(i)
        parent[i] = oya
        #print(oya)
        if oya in group:
            group[oya] = group[oya]+1
        else:
            group[oya]=1
     
    for i in range(K):
        A,B = list(map(int,input().split(' ')))
        if find(A)==find(B):
            bad_list[A]+=1
            bad_list[B]+=1
        
        #union(A,B)
     
     
     
    #print(parent)
    #print('parent')
     
    #print('friend')
    #print(friend_list)
    #print('bad')
    #print(bad_list) 
    #print(group)
     
    kouho = [0]*N
     
    for i in range(1,N+1):
        oya = find(i)
        abc = group[oya]-friend_list[i]-bad_list[i]-1
        kouho[i-1] = abc
     
    for k in kouho:
        print(k,end=" ")
    print()
     
    #print(parent)

Submission status: Runtime Error

Solution code:
N,M,K=map(int,input().split())
par=[i for i in range(N+1)]
siz=[1 for i in range(N+1)]
fre=[0 for i in range(N+1)]
blo=[0 for i in range(N+1)]
rank=[0 for i in range(N+1)]

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

#木をつなぐ
def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        par[a]=b
        siz[b]+=siz[a]

def size(a):
    return siz[find(a)]

def same(a,b):
    return find(a)==find(b)

for i in range(M):
    A,B=map(int,input().split())
    union(A,B)
    fre[A]+=1
    fre[B]+=1
for i in range(K):
    C,D=map(int,input().split())
    if(same(C,D)):
        blo[C]+=1
        blo[D]+=1

for i in range(1,N+1):
    print(size(i)-fre[i]-blo[i]-1,end=' ')

Submission status: Runtime Error

Solution code:
import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    n, m, k = map(int, input().split())
    fgraph = [list() for i in range(n)]
    bgraph = [list() for i in range(n)]
    cgraph = [list() for i in range(n)]


    seen = [None]*n
    def dfs(graph,s):
        seen[s] = s+1
        for i in range(len(graph[s])):
            if seen[graph[s][i]-1]:
                continue
            dfs(graph, graph[s][i]-1)

    for i in range(m):
        a,b = map(int, input().split())

        fgraph[a-1].append(b)
        fgraph[b-1].append(a)

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

    # print(fgraph)
    #print(bgraph)
    rk = [list()]*n
    for i in range(n):
        seen = [None]*n
        dfs(fgraph, i)
        rk[i] = seen
    
    # print(rk)
    # print(fgraph)
    for i in range(n):
        non = {None}
        me = {i+1}
        srk = set(rk[i])-non
        bg = set(bgraph[i])
        fg = set(fgraph[i])

        print(len(srk-bg-fg-me))
        
    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

friend_list = [0]*(N+1)
bad_list = [0]*(N+1)
group = {}

parent = [i for i in range(N+1)]

def union(x,y):
    x = find(x)
    y = find(y)
    parent[x] = y

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



for i in range(M):
    A,B = list(map(int,input().split(' ')))
    friend_list[A]+=1
    friend_list[B]+=1
    
    union(A,B)

for i in range(1,N+1):
    oya = find(i)
    parent[i] = oya
    #print(oya)
    if oya in group:
        group[oya] = group[oya]+1
    else:
        group[oya]=1

for i in range(K):
    A,B = list(map(int,input().split(' ')))
    if find(A)==find(B):
        bad_list[A]+=1
        bad_list[B]+=1
    
    #union(A,B)



#print(parent)
#print('parent')

#print('friend')
#print(friend_list)
#print('bad')
#print(bad_list) 
#print(group)

kouho = [0]*N

for i in range(1,N+1):
    oya = find(i)
    abc = group[oya]-friend_list[i]-bad_list[i]-1
    kouho[i-1] = abc

for k in kouho:
    print(k,end=" ")
print()

#print(parent)

Submission status: Runtime Error

Solution code:
import collections
import sys

import numpy as np

readline = sys.stdin.buffer.readline


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


def main():
    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)]

    E = UnionFind(N)

    ans = [0 for _ in range(N)]
    for a, b in AB:
        a -= 1
        b -= 1
        E.unite(a, b)
        ans[a] -= 1
        ans[b] -= 1

    for i in range(N):
        E.find(i)

    ll = collections.defaultdict(int)
    for i in E.par:
        ll[i] += 1

    for i in range(N):
        ans[i] += ll[E.par[i]] - 1

    for i, j in CD:
        i -= 1
        j -= 1
        if E.same(i, j):
            ans[i] -= 1
            ans[j] -= 1

    print(*ans)


main()

Submission status: Runtime Error

Solution code:

#####

# import numpy as np
# from numpy import newaxis, float32, float64, int32, int64, int16, int8, uint8, uint32, complex64, complex128
from collections import defaultdict

#####

def getIntList(inp):
	return [int(_) for _ in inp]
	

from sys import stdin

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs


def st(x,y):
	return tuple(sorted([x,y]))

def getGroup(groups, i):
	if i not in groups:
		groups[i]=i
	return groups[i]
		

def search(i0, visited, fr):
	for i1 in fr[i0]:
		if i1 not in visited:
			visited.add(i1)
			search(i1, visited, fr)

		
def main(inputs):
	n=int(inputs[0][0])
	m=int(inputs[0][1])
	k=int(inputs[0][2])
	
	fr=defaultdict(set)
	for i in range(m):
		a=int(inputs[i+1][0])-1
		b=int(inputs[i+1][1])-1
		fr[a].add(b)
		fr[b].add(a)
		
	bl=defaultdict(set)
	for i in range(k):
		a=int(inputs[i+1+m][0])-1
		b=int(inputs[i+1+m][1])-1
		bl[a].add(b)
		bl[b].add(a)
	
	for i0 in range(n):
		visited=set([i0])
		search(i0, visited, fr)
		can=visited-fr[i0]-bl[i0]
		num=len(can)-1
# 		print(i0, num)
		print(num, end="")
		if i0<n-1: print(" ", end="")
	
	

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)

Submission status: Runtime Error

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

parents = [-1] * N
friend = [set() for _ in range(N)]

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

def union(x, y):
	x = find(x)
	y = find(y)

	if x == y:
		return

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

	parents[x] += parents[y]
	parents[y] = x

for _ in range(M):
	A, B = map(int, input().split())
	union(A-1, B-1)
	friend[A-1].add(B-1)
	friend[B-1].add(A-1)

a = [-parents[find(i)]-len(friend[i])-1 for i in range(N)]

for _ in range(K):
	C, D = map(int, input().split())
	if find[C-1] == find[D-1]:
		a[C-1] -= 1
		a[D-1] -= 1
print(*a)

Submission status: Runtime Error

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

fmap = [[0 for i2 in range(N)] for i1 in range(N)]

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

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

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

for aa,bb in ab:
    if frno[aa] == -1 and frno[bb] == -1:
        frn = min(aa,bb)
        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[aa]) > len(fring[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
            del fring[frnfrom]

for k in range(len(fring)):
    for i in range(len(fring[k])-1):
        for j in range(i+1,len(fring[k])):
            f1 = fring[k][i]
            f2 = fring[k][j]
            if f1 > f2:
                f1,f2 = f2,f1
            if fmap[f1-1][f2-1] == 0:
                fcnum[f1] += 1
                fcnum[f2] += 1
                fmap[f1-1][f2-1] = frno[f1]

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

Submission status: Runtime Error

Solution code:
slct='D'

# C
if slct=='C':
    N,M=map(int,input().split())
    cnd=[tuple(int(i) for i in input().split()) for j in range(M)]
    ans=-1
    for n in range(10**N):
        # print(n)
        flag=True
        n_str=str(n)
        if len(n_str)!= N:
            continue
        for s,c in cnd:
            if n_str[s-1]!=str(c):
                # print(n_str[s-1],c)
                flag=False
                break
        if flag:
            ans=n
            break
    print(ans)
# D
elif slct=='D':
    # 友達関係の無向グラフを作る
    #
    N,M,K=map(int,input().split())
    blk=[[] for _ in range(N)]
    fnd=[[] for _ in range(N)]

    pnt=[i for i in range(N)]

    def root(n):
        if pnt[n]==n:
            return n
        else:
            pnt[n]=root(pnt[n])
            return pnt[n]
    
    def issame(m,n):
        return root(m)==root(n)
    
    def union(m,n):
        if issame(m,n):
            pass
        else:
            pnt[root(m)]=root(n)
        
    for _ in range(M):
        A,B=map(int,input().split())
        fnd[A-1].append(B-1)
        fnd[B-1].append(A-1)
        union(A-1,B-1)
    for _ in range(K):
        C,D=map(int,input().split())
        blk[C-1].append(D-1)
        blk[D-1].append(C-1)

    for i in range(N):
        ans=0
        for j in range(N):
            if i==j: # 自分
                continue
            if i in blk[j]: #ブロック関係である
                continue
            if i in fnd[j]: # 直接の友達関係である
                continue
            if issame(i,j): # 間接の友達関係である
                ans+=1
        print(ans)

Submission status: Runtime Error

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

fmap = [[0 for i2 in range(N)] for i1 in range(N)]

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

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

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

for aa,bb in ab:
    if frno[aa] == -1 and frno[bb] == -1:
        frn = min(aa,bb)
        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[aa]) > len(fring[bb]):
                frnto = frno[aa]
                frnfrom = frno[bb]
            else:
                frnto = frno[bb]
                frnfrom = frno[aa]
            for mvf in fring[frnfrom]:
                fring[frnto].append(mvf)
                frno[mvf] = frnto
            del fring[frnfrom]

for k in range(len(fring)):
    for i in range(len(fring[k])-1):
        for j in range(i+1,len(fring[k])):
            f1 = fring[k][i]
            f2 = fring[k][j]
            if f1 > f2:
                f1,f2 = f2,f1
            if fmap[f1-1][f2-1] == 0:
                fcnum[f1] += 1
                fcnum[f2] += 1
                fmap[f1-1][f2-1] = frno[f1]

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

Submission status: Runtime Error

Solution code:
import collections
import sys

sys.setrecursionlimit(1000000)
N,M,K = map(int,input().split())
graph = {}
block = collections.defaultdict(set)
for _ in range(M):
    a,b =map(int,input().split())
    if a not in graph:
        graph[a] = set()
    if b not in graph:
        graph[b] = set()
    graph[a].add(b)
    graph[b].add(a)
for _ in range(K):
    a,b =map(int,input().split())
    if a not in block:
        block[a] = set()
    if b not in block:
        block[b] = set()
    block[a].add(b)
    block[b].add(a)

counter = collections.defaultdict(set)
dic = {}
def dfs(i,visit,c,start):
    visit.add(i)
    c.add(i)
    dic[i] = start
    for g in graph[i]:
        if g not in visit:
            dfs(g,visit,c,start)
ans = [0]*N
visit =set()
for i in range(N):
    if i + 1 not in visit:
        dfs(i + 1,visit,counter[i+1],i + 1)
    #print(len(counter[dic[i + 1]]))
    tmp = counter[dic[i + 1]] - block[i + 1]
    tmp = tmp - graph[i + 1]
    ans[i] = len(tmp) -1
#print(ans)
for i in range(len(ans) -1):
    print(ans[i], end=" ")
print(ans[-1])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
def input(): return sys.stdin.readline().strip()

class UnionFind:
    def __init__(self, n):
        self.par = list(range(n))
        self.rank = [0]*n
        self._size = [1]*n

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

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

        if x == y:
            return

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

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

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

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


def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

N, M, K = l_in()

uni = UnionFind(N)

friends = []

for _ in range(M):
    a,b = l_in()
    uni.union(a-1, b-1)
    friends.append((a-1, b-1))

blocks = []

for _ in range(K):
    c,d = l_in()
    blocks.append((c-1, d-1))

res = [uni.size(i)-1 for i in range(N)]

for a,b in friends:
    res[a] -= 1
    res[b] -= 1

for c,d in blocks:
    if uni.same_check(c, d):
        res[c] -= 1
        res[d] -= 1

print_l(res)

Submission status: Runtime Error

Solution code:
N, M, K = map(int, input().split())
uf = UnionFind(N)
a = [0] * M
b = [0] * M
for i in range(M):
    a[i], b[i] = map(int, input().split())
    uf.union(a[i]-1, b[i]-1)

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

for i in range(M):
    if uf.same(a[i]-1, b[i]-1):
        ans[a[i]-1] -= 1
        ans[b[i]-1] -= 1

for i in range(K):
    c, d = map(int, input().split())
    if uf.same(c-1, d-1):
        ans[c-1] -= 1
        ans[d-1] -= 1

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

Submission status: Runtime Error

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

r = [n-1] * n

for _ in range(m):
  #print(list(map(int, input().split())))
  friends = list(map(int, input().split()))
  r[friends[0]-1] -= 1
  r[friends[1]-1] -= 1
  
for _ in range(k):
  #print(list(map(int, input().split())))
  friends = list(map(int, input().split()))
  r[friends[0]-1] -= 1
  r[friends[1]-1] -= 1

print(" ".join(r))

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, num):
        self.par = [i for i in range(num)]
    
    def find(self, x):
        if self.par[x] != x:
            self.par[x] = self.find(self.par[x])
        return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # if x == y:
        #     return True
        self.par[x] = y
        # return False
    
    def same(self, x,y):
        return self.find(x) == self.find(y)

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

uf = UnionFind(n)

from collections import Counter

AB = [list(map(int,input().split())) for _ in range(m)]
CD = [list(map(int,input().split())) for _ in range(k)]

for a,b in AB:
    a, b = a-1, b-1
    uf.union(a, b)

for i in range(n):
    uf.find(i)

cnt = Counter(uf.par)
ans = [cnt[uf.par[i]] -1 for i in range(n)]

def res(ls):
    for e1, e2 in ls:
        e1, e2 = e1-1, e2-1
        if uf.same(e1, e2):
            ans[e1] -= 1
            ans[e2] -= 1
res(AB)
res(CD)
print(*ans)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, num):
        self.par = [i for i in range(num)]
    
    def find(self, x):
        if self.par[x] != x:
            self.par[x] = self.find(self.par[x])
        return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return True
        self.par[x] = y
        return False
    
    def same(self, x,y):
        return self.find(x) == self.find(y)

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

uf = UnionFind(n)

from collections import Counter

AB = [list(map(int,input().split())) for _ in range(m)]
CD = [list(map(int,input().split())) for _ in range(k)]

for a,b in AB:
    a, b = a-1, b-1
    uf.union(a, b)

for i in range(n):
    uf.find(i)

cnt = Counter(uf.par)
ans = [cnt[uf.par[i]] -1 for i in range(n)]

def res(ls):
    for e1, e2 in ls:
        e1, e2 = e1-1, e2-1
        if uf.same(e1, e2):
            ans[e1] -= 1
            ans[e2] -= 1
res(AB)
res(CD)
print(*ans)

Submission status: Runtime Error

Solution code:
import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    n, m, k = map(int, input().split())
    fgraph = [list() for i in range(n)]
    bgraph = [list() for i in range(n)]
    cgraph = [list() for i in range(n)]


    seen = [False]*n
    def dfs(graph,s,t):
        seen[s] = True
        if t+1 in graph[s]:
            return True
        for i in range(len(graph[s])):
            if seen[graph[s][i]-1]:
                continue
            if dfs(graph, graph[s][i]-1, t):
                return True
        return False

    for i in range(m):
        a,b = map(int, input().split())

        fgraph[a-1].append(b)
        fgraph[b-1].append(a)

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

    # print(fgraph)
    #print(bgraph)

    for i in range(n):
        for j in range(i,n):
            if j == i or j+1 in bgraph[i] or j+1 in fgraph[i]:
                continue
            # print(i+1,j+1)
            seen = [False]*n
            if dfs(fgraph, i, j):
                cgraph[i].append(j)
                cgraph[j].append(i)
            # i+1 から j+1 への経路の存在を探索する
    print(cgraph)    
    for i in range(n):

        print(len(set(cgraph[i])))
    
    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    n, m, k = map(int, input().split())
    fgraph = [list() for i in range(n)]
    bgraph = [list() for i in range(n)]
    cgraph = [list() for i in range(n)]


    seen = [False]*n
    def dfs(graph,s,t):
        seen[s] = True
        if t+1 in graph[s]:
            return True
        for i in range(len(graph[s])):
            if seen[graph[s][i]-1]:
                continue
            if dfs(graph, graph[s][i]-1, t):
                return True
        return False

    for i in range(m):
        a,b = map(int, input().split())

        fgraph[a-1].append(b)
        fgraph[b-1].append(a)

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

    # print(fgraph)
    #print(bgraph)

    for i in range(n):
        for j in range(i,n):
            if j == i or j+1 in bgraph[i] or j+1 in fgraph[i]:
                continue
            # print(i+1,j+1)
            seen = [False]*n
            if dfs(fgraph, i, j):
                cgraph[i].append(j)
                cgraph[j].append(i)
            # i+1 から j+1 への経路の存在を探索する
    #print(cgraph)    
    for i in range(n):

        print(len(set(cgraph[i])))
    
    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return



def main():
    n, m, k = map(int, input().split())
    fgraph = [list() for i in range(n)]
    bgraph = [list() for i in range(n)]
    cgraph = [list() for i in range(n)]


    seen = [False]*n
    def dfs(graph,s,t):
        seen[s] = True
        if t+1 in graph[s]:
            return True
        for i in range(len(graph[s])):
            if seen[graph[s][i]-1]:
                continue
            if dfs(graph, graph[s][i]-1, t):
                return True
        return False

    for i in range(m):
        a,b = map(int, input().split())

        fgraph[a-1].append(b)
        fgraph[b-1].append(a)

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

    # print(fgraph)
    #print(bgraph)

    for i in range(n):
        for j in range(n):
            if j == i or j+1 in bgraph[i] or j+1 in fgraph[i]:
                continue
            # print(i+1,j+1)
            seen = [False]*n
            if dfs(fgraph, i, j):
                cgraph[i].append(j)
                cgraph[j].append(i)
            # i+1 から j+1 への経路の存在を探索する
    #print(cgraph)    
    for i in range(n):

        print(len(set(cgraph[i])))
    
    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n,m,k=map(int,input().split())
w=[i for i in range(n+1)]
s=[1]*(n+1)
g=[list(map(int,input().split()))for i in range(n)]
def root(x):
    if w[x]==x:
        return x
    x=w[x]
    return root(w[x])
def unite(x,y):
    x=root(x)
    y=root(y)
    if x!=y:
        if s[x]<s[y]:
            w[x]=y
            s[y]+=1
        else:
            w[y]=x
            s[x]+=1
for i in range(m):
    a,b=g[i][0],g[i][1]
    unite(a,b)
for i in range(1,n+1):
    w[i]=root(i)
    s[i]=s[w[i]]
for i in range(m):
    s[g[i][0]]-=1
    s[g[i][1]]-=1
for i in range(k):
    a,b=map(int,input().split())
    if w[a]==w[b]:
        s[a]-=1
        s[b]-=1
for i in range(1,n+1):s[i]-=1
print(*s[1:])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
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)]
con = [1 for _ in range(n+1)]
uni = [-1 for i in range(n+1)]

def root(num, pea):
    if pea[num] < 0:
        return num
    else:
        pea[num] = root(pea[num], pea)
        return pea[num]

for i in range(m):
    a, b = ab[i]
    con[a] += 1
    con[b] += 1
    if uni[a] != uni[b] or uni[a] < 0 or uni[b] < 0:
        root_a = root(a, uni)
        root_b = root(b, uni)
        root_a, root_b = sorted([root_a, root_b])
        uni[root_a] += uni[root_b]
        uni[root_b] = root_a
        root_b = root(root_b, uni)

for i in range(k):
    c, d = cd[i]
    if root(c, uni) == root(d, uni):
        con[c] += 1
        con[d] += 1

result = []
for i in range(1, n+1):
    root_i = root(i, uni)
    result.append(-uni[root_i]-con[i])
print(*result)