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: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353

class UnionFind:
    def __init__(self, size=None, nodes=None):
        """
        size か nodes どっちか指定。
        nodes は set、size は list を使う。
        :param int size:
        :param collections.Iterable nodes:
        """
        assert size is not None or nodes is not None
        if size is not None:
            self._parents = [i for i in range(size)]
            self._ranks = [0 for _ in range(size)]
            self._sizes = [1 for _ in range(size)]
        else:
            self._parents = {k: k for k in nodes}
            self._ranks = {k: 0 for k in nodes}
            self._sizes = {k: 1 for k in nodes}

    def unite(self, x, y):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        """
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return

        # rank が小さい方が下
        if self._ranks[x] > self._ranks[y]:
            # x が root
            self._parents[y] = x
            self._sizes[x] += self._sizes[y]
        else:
            # y が root
            self._parents[x] = y
            self._sizes[y] += self._sizes[x]
            if self._ranks[x] == self._ranks[y]:
                self._ranks[y] += 1

    def root(self, x):
        """
        x が属する木の root
        :param x:
        """
        if self._parents[x] == x:
            return x
        self._parents[x] = self.root(self._parents[x])
        return self._parents[x]

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        """
        return self._sizes[self.root(x)]


N, M, K = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
CD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(K)]

uf = UnionFind(size=N + 1)
for a, b in AB:
    uf.unite(a, b)

friends = [0] * (N + 1)
blocks = [0] * (N + 1)
for a, b in AB:
    if uf.root(a) == uf.root(b):
        friends[a] += 1
        friends[b] += 1
for a, b in CD:
    if uf.root(a) == uf.root(b):
        blocks[a] += 1
        blocks[b] += 1

ans = []
for i in range(1, N + 1):
    cnt = uf.size(i) - friends[i] - blocks[i] - 1
    ans.append(cnt)
print(*ans)

Submission status: Runtime Error

Solution code:
class UFNode:
    def __init__(self, ID):
        self.ID = ID
        self.parent = None
        # size of connected component
        self.cc_size = 1

class UFTree:
    def __init__(self, N):
        self.N = N
        self.nodes = [ UFNode(i) for i in range(N) ]

    def get_root(self, node):
        if node.parent is None:
            return node
        root = self.get_root(node.parent)
        node.parent = root
        return root

    def same(self, node1, node2):
        root1 = self.get_root(node1)
        root2 = self.get_root(node2)
        return root1.ID == root2.ID

    def merge(self, node1, node2):
        root1 = self.get_root(node1)
        root2 = self.get_root(node2)

        if root1.ID == root2.ID:
            return

        root1.parent = root2
        root2.cc_size += root1.cc_size

    def get_cc_size(self, node):
        root = self.get_root(node)
        return root.cc_size

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

    friend_list = [[] for i in range(N) ]
    block_list = [[] for i in range (N)]

    tree = UFTree(N)

    # friend
    for i in range(M):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        friend_list[a].append(b)
        friend_list[b].append(a)
        tree.merge(tree.nodes[a], tree.nodes[b])

    # blocked
    for i in range(K):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        if not tree.same(tree.nodes[a], tree.nodes[b]):
            continue

        # 同じ連結成分であれば後の排除処理のためにリストに追加する
        block_list[a].append(b)
        block_list[b].append(a)

    result = ""
    for i in range(N):
        n = tree.nodes[i]
        result += str(tree.get_cc_size(n) - (len(friend_list[i]) + len(block_list[i]) + 1)) + " "

    print(result[:-1])

main()

Submission status: Runtime Error

Solution code:
from collections import Counter

class Unionfind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * (n+1)
        
    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())
uf = Unionfind(N)
f = [0 for _ in range(N)]
n = [0 for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uf.union(a, b)
    
    f[a] += 1
    f[b] += 1
    
for _ in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if(uf.same(c, d)):
        n[c] += 1
        n[d] += 1
    
ans = []
for i in range(N):
    ans.append(uf.size(i)-f[i]-n[i]-1)
    
print(*ans)v

Submission status: Runtime Error

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

fre=[[] for _ in range(n+1)]
bro=[[] for _ in range(n+1)]

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

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

ans=[]

x=[-1]*(n+1)

def s(z,y):
    if x[y]>0:
        return
    x[y]=z
    for i in fre[y]:
        if x[i]==-1:
            s(z,i)

for i in range(1,n+1):
    s(i,i)

g=[0]*(n+1)
for i in range(1,n+1):
    g[x[i]]+=1
for i in range(1,n+1):
    g[i]=g[x[i]]

for i in range(1,n+1):
    aa=g[i]-1
    aa-=len(fre[i])
    for j in bro[i]:
        if x[i]==x[j]:
            aa-=1
    ans.append(str(aa))
print(" ".join(ans))

Submission status: Runtime Error

Solution code:
# Union Find

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 is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]
    
f=lambda:map(int,input().split())
N,M,K=f()
uf=UnionFind(N)
check=[[0]*(N+1) for _ in [0]*(N+1)]
bro=[0]*(N+1)
AB=[]
for _ in [0]*M:
    a,b=f()
    AB.append((a,b))
    check[b][a]==1
    uf.unite(a,b)
for a,b in AB:
    if uf.is_same_group(a,b):
        bro[a]+=1
        bro[b]+=1
for _ in [0]*K:
    c,d=f()
    check[d][c]==1
    if uf.is_same_group(c,d):
        bro[c]+=1
        bro[d]+=1
for i in range(1,N+1):
    print(uf.count(i)-1-bro[i])

Submission status: Runtime Error

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

f_adj_list = [[] for i in range(n)]
b_adj_list = [[] for i in range(n)]

for i in range(m):
  _, __ = map(int, input().split())
  _ -= 1
  __ -= 1
  f_adj_list[_].append(__)
  f_adj_list[__].append(_)
  
for j in range(k):
  _, __ = map(int, input().split())
  _ -= 1
  __ -= 1
  b_adj_list[_].append(__)
  b_adj_list[__].append(_)
  
  
group_id = [None for i in range(n)]
for i in range(n):
  # i から DFS
  newly_visited = [i]
  group_id[i] = i
  while len(newly_visited) > 0:
    now = newly_visited.pop()
    for j in f_adj_list[now]:
      if group_id[j] is not None: continue
      newly_visited.append(j)
      group_id[j] = i

# group_id
# print(group_id)

# 連結成分のサイズ
from collections import Counter
cnt = Counter(group_id)
# cnt[5] = 7

ans_list = []
for i in range(n):
  ans = cnt[group_id[i]]
  ans -= 1 # 自分自身
  ans -= len(f_adj_list[i]) # 直接の友達
  for j in b_adj_list[i]:
    if group_id[i] == group_id[j]:
      ans -= 1
  ans_list.append(ans)

print(" ".join(ans_list))

Submission status: Runtime Error

Solution code:
package main

import (
	"bufio"
	"fmt"
	"io"
	"math"
	"os"
	"strconv"
	"strings"

)


func main() {
	solve(os.Stdin, os.Stdout)
}

type ReaderEx struct {
	baseScanner *bufio.Scanner
	words       []string
	nextWordIdx func() int
	initWordIdx func(int)
}

func NewScannerEx(stdin io.Reader) *ReaderEx {
	var this ReaderEx
	var idx int
	var wordsCnt int
	this.baseScanner = bufio.NewScanner(stdin)
	this.baseScanner.Buffer(make([]byte, 0), 1E+11)
	this.nextWordIdx = func() int {
		cur := idx
		idx = (idx + 1) % wordsCnt
		return cur
	}
	this.initWordIdx = func(wc int) {
		idx = 0
		wordsCnt = wc
	}
	return &this
}

func (me *ReaderEx) Scan(doSplit bool) (isScanned bool) {
	isScanned = me.baseScanner.Scan()
	if doSplit {
		me.words = strings.Fields(me.baseScanner.Text())
	} else {
		me.words = []string{me.baseScanner.Text()}
	}
	me.initWordIdx(len(me.words))
	return
}

func (me *ReaderEx) nextBytes() []byte {
	return []byte(me.words[me.nextWordIdx()])
}
func (me *ReaderEx) nextString() string {
	return me.words[me.nextWordIdx()]
}

type StringArray []string

func (me *ReaderEx) nextStringArray() StringArray {
	return me.words[me.nextWordIdx():]
}

func (me StringArray) toStrings() []string {
	return me
}

func (me StringArray) toInts() []int {
	strValues := me.toStrings()
	values := make([]int, len(strValues))
	for i, v := range strValues {
		n, err := strconv.Atoi(v)
		if err != nil {
			panic(err)
		}
		values[i] = n
	}
	return values
}
func (me *ReaderEx) nextInt() int {
	n, err := strconv.Atoi(me.words[me.nextWordIdx()])

	defer func() {
		if err != nil {
			panic(fmt.Sprintf("getInt(%d)", n))
		}
	}()
	return n
}

func pow(x, y, mod int) (ans int) {

	ans = 1
	for bit := 1 << uint(math.Floor(math.Log2(float64(y)))); ; bit >>= 1 {
		if y&bit != 0 {
			ans *= x
			if mod > 0 {
				ans %= mod
			}
		}
		if bit <= 1 {
			return
		}
		ans *= ans
		if mod > 0 {
			ans %= mod
		}
	}
}

type factType struct {
	prime int
	count int
}

func fact(n int) (facts []*factType) {

	for i := 2; i*i <= n; i++ {
		if n%i == 0 {
			fa := factType{prime: i}
			for n%fa.prime == 0 {
				n /= fa.prime
				fa.count++
			}
			facts = append(facts, &fa)
		}
	}
	if n > 1 {
		facts = append(facts, &factType{prime: n, count: 1})
	}
	return facts
}
func dec2bin(n int) (ret []bool) {
	for bit := 1 << uint(math.Floor(math.Log2(float64(n)))); ; bit >>= 1 {
		ret = append(ret, n&bit != 0)

		if bit <= 1 {
			return
		}
	}

}

func abs(v int) int {
	if v < 0 {
		v = -v
	}
	return v
}

func b2i(b bool) (i int) {
	if b {
		i = 1
	} else {
		i = 0
	}
	return
}

type Group struct {
	parent *Group
	count  int
}

func (g *Group) top() *Group {
	his := []*Group{}
	cur := g
	for cur.parent != nil {
		his = append(his, cur)
		cur = cur.parent
	}
	for _, h := range his {
		h.parent = cur
	}
	return cur
}

type Person struct {
	friends      *Group
	badfriendCnt int
}

func NewPerson() Person {
	return Person{friends: &Group{count: 1}}
}

func (person *Person) makeFriendWith(p *Person) {
	if person.friends.top() != p.friends.top() {
		person.friends.top().count += p.friends.top().count
		p.friends.top().parent = person.friends.top()
	}

}

func solve(stdin io.Reader, stdout io.Writer) {

	r := NewScannerEx(stdin)
	r.Scan(true)
	n, m, k := r.nextInt(), r.nextInt(), r.nextInt()

	persons := make([]Person, n)
	for i := range persons {
		persons[i] = NewPerson()
	}

	for i := 0; i < m; i++ {
		r.Scan(true)
		p1, p2 := &persons[r.nextInt()-1], &persons[r.nextInt()-1]
		p1.makeFriendWith(p2)
		p1.badfriendCnt++
		p2.badfriendCnt++
	}

	for i := 0; i < k; i++ {
		r.Scan(true)
		p1, p2 := &persons[r.nextInt()-1], &persons[r.nextInt()-1]
		if p1.friends.top() == p2.friends.top() {
			p1.badfriendCnt++
			p2.badfriendCnt++
		}
	}

	ans := make([]string, n)
	for i, p := range persons {
		ans[i] = strconv.Itoa(p.friends.top().count - p.badfriendCnt - 1)
	}
	fmt.Fprintln(stdout, strings.Join(ans, " "))
}

Submission status: Runtime Error

Solution code:
class Union:
    def __init__(self, n):
        self.group = list(range(n + 1))
        self.items = [set((i,)) for i in range(n + 1)]

    def get(self, i):
        return self.items[self.group[i]]

    def merge(self, a, b):
        pa, pb = self.group[a], self.group[b]
        self.group[pb] = pa
        for i in self.items[pb]:
            self.group[i] = pa
        self.items[pa].update(self.items[pb])
        self.group[b] = pa

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

friend = [set() for _ in range(n + 1)]
block = [set() for _ in range(n + 1)]
union = Union(n)

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

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

ans = []

for i in range(1, n + 1):
    f = friend[i]
    candidate = set()
    for fi in f:
        candidate.update(union.get(fi))
    candidate = candidate - block[i] - friend[i]
    candidate.remove(i)
    ans.append(len(candidate))

print(*ans)

Submission status: Runtime Error

Solution code:
class Union:
    def __init__(self, n):
        self.group = list(range(n + 1))
        self.items = [set((i,)) for i in range(n + 1)]

    def get(self, i):
        return self.items[self.group[i]]

    def merge(self, a, b):
        pa, pb = self.group[a], self.group[b]
        self.group[pb] = pa
        for i in self.items[pb]:
            self.group[i] = pa
        self.items[pa].update(self.items[pb])
        self.group[b] = pa

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

friend = [set() for _ in range(n + 1)]
block = [set() for _ in range(n + 1)]
union = Union(n)

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

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

ans = []

for i in range(1, n + 1):
    f = friend[i]
    candidate = set()
    for fi in f:
        candidate.update(union.get(fi))
    candidate = candidate - block[i] - friend[i]
    candidate.remove(i)
    ans.append(len(candidate))

print(*ans)

Submission status: Runtime Error

Solution code:
N,M,K = map(int, input().split())
par = [i for i in range(N+1)]
size = [1 for _ in range(N+1)]
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y
    size[y] = size[x] + size[y]
    size[x] = 0
friend = [set() for i in range(N+1)]
for i in range(M):
    a,b =map(int,input().split())
    unite(a,b)
    friend[a].add(b)
    friend[b].add(a)
for j in range(K):
    a,b = map(int,input().split())
    if same(a,b):
        friend[a].add(b)
        friend[b].add(a)
Answer = []
for k in range(1,N+1):
    Ans = size[find(k)] - len(friend[k]) - 1
    Answer.append(Ans)
print(*Answer)

Submission status: Runtime Error

Solution code:
N,M,K = list(map(int, input().split()))
par = [i for i in range(N+1)]
size = [1 for _ in range(N+1)]
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y
    size[y] = size[x] + size[y]
    size[x] = 0
friend = [set() for i in range(N+1)]
for i in range(M):
    a,b =map(int,input().split())
    unite(a,b)
    friend[a].add(b)
    friend[b].add(a)
for j in range(K):
    a,b = map(int,input().split())
    if same(a,b):
        friend[a].add(b)
        friend[b].add(a)
Answer = []
for k in range(1,N+1):
    Ans = size[find(k)] - len(friend[k]) - 1
    Answer.append(Ans)
print(*Answer)

Submission status: Runtime Error

Solution code:
from collections import deque
N,M,K=map(int,input().strip().split())
AB=[list(map(int,input().strip().split())) for _ in range(M)]
CD=[list(map(int,input().strip().split())) for _ in range(K)]

fe=[0 for _ in range(N)]
g=[-1 for _ in range(N)]
dp=[list() for _ in range(N)]
for m in range(M):
    fe[AB[m][0]-1]+=1
    fe[AB[m][1]-1]+=1
    g[AB[m][0]-1]=0
    g[AB[m][1]-1]=0
    dp[AB[m][0]-1].append(AB[m][1])
    dp[AB[m][1]-1].append(AB[m][0])
    
for k in range(K):
    fe[CD[k][0]-1]+=1
    fe[CD[k][1]-1]+=1
    g[CD[k][0]-1]=0
    g[CD[k][1]-1]=0

q=deque([AB[0][0]])
i=1
for n in range(N):
	if g[n]==0:
    	q.append(n)
    while q:
        tmp=q.popleft()
        g[tmp-1]=i
        for e in dp[tmp-1]:
            if g[e-1]==0:
                q.append(e)
    i+=1

print(g)
d={}
for k in range(1,i+1):
    d[k]=g.count(i)
d[-1]=0
ans=[]
for n in range(N):
    ans.append(max(0,d[g[n]]-fe[n]))
print(" ".join(list(map(str,ans))))

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
friendships = [[] for _ in range(n)]
for _ in range(m):
  a, b = map(int, input().split())
  friendships[a-1].append(b-1)
  friendships[b-1].append(a-1)
blockships = [[] for _ in range(n)]
for _ in range(k):
  c, d = map(int, input().split())
  blockships[c-1].append(d-1)
  blockships[d-1].append(c-1)
# assign users (id) for connected component, according to friendships
# also increment a counter for size of each component
component_id = [-1]*n
component_size = dict()
def search(node, parent_id):
  if component_id[node] != -1:
    return
  component_id[node] = parent_id
  component_size[parent_id] = component_size.get(parent_id, 0) + 1
  for other in friendships[node]:
    search(other, parent_id)
for initial_node in range(n):
  search(initial_node, initial_node)
# calculate number of suggestions for each node
for node in range(n):
  suggestions = 0
  current_id = component_id[node]
  suggestions += component_size[current_id] - 1
  suggestions -= len(friendships[node])
  suggestions -= sum(int(component_id[other] == current_id) for other in blockships[node])
  print(suggestions, end=" ")

Submission status: Runtime Error

Solution code:
import sys


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

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

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

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1


def main():
    n, m, k = map(int, sys.stdin.buffer.readline().split())
    uf = UnionFind(n)
    fb = [0]*n
    i = 0
    for x in sys.stdin.buffer.readlines():
        print(uf.table)
        if i < m:
            a, b = map(int, x.split())
            fb[a-1] += 1
            fb[b-1] += 1
            uf.union(a-1, b-1)
        else:
            c, d = map(int, x.split())
            if uf._root(c-1) == uf._root(d-1):
                fb[c-1] += 1
                fb[d-1] += 1
        i += 1

    ans = [-uf.table[uf._root(i)]-1-fb[i] for i in range(n)]
    print(*ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
def main():
    import sys

    sys.setrecursionlimit(10 ** 5)

    def dfs(now: int, chain: set):
        """nowを現在の頂点として，つながっている頂点をglaphに集合として記録"""
        if seen[now]:
            return chain
        seen[now] = i
        for next in friends[now]:
            chain.add(now)
            dfs(next, chain)

    N, M, K = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in [0] * M]
    CD = [tuple(map(int, input().split())) for _ in [0] * K]

    friends = [set() for _ in [0] * (N + 1)]
    for f in AB:
        friends[f[0]].add(f[1])
        friends[f[1]].add(f[0])
    blocks = [set() for _ in [0] * (N + 1)]
    for b in CD:
        blocks[b[0]].add(b[1])
        blocks[b[1]].add(b[0])

    friends_chain = []
    seen = [0] * (N + 1)
    cnt = 1
    for i in range(1, N + 1):
        if not seen[i]:
            glaph = set()
            dfs(i, glaph)
            friends_chain.append(glaph)
            cnt += 1

    ans = [0] * (N + 1)
    for person in range(1, N + 1):
        res = set(friends_chain[seen[person] - 1])
        for block in blocks[person]:
            res.discard(block)
        for friend in friends[person]:
            res.discard(friend)
        ans[person] = len(res) - 1
    
    for hoge in ans[1:]:
        print(hoge, end=' ')


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import Counter

class union_find():
    def __init__(self,n):
        self.n=n
        ##親要素のノード番号を格納。par[x]==xのときそのノードは根
        ##親とはその上にノードなし！！　
        self.par=[-1 for i in range(n)]
        self.rank=[0]*(n)

    def find(self,x):
        if self.par[x]<0:
            return x
        else:
            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

        elif self.rank[x]>self.rank[y]:
          self.par[y]=x
        else:
          self.par[x]=y
          ##同じなら片方を伸ばす
          if self.rank[x]==self.rank[y]:
            self.rank[y]+=1

    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.par) if x<0]
    
    def all_group_member(self):
      return {r:self.members(r) for r in self.roots()}
      
n,m,k=map(int,input().split())
uf=union_find(n)
good=[[]for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  uf.union(a-1,b-1)
  good[a-1].append(b-1)
  good[b-1].append(a-1)
  
  
bad=[[]for _ in range(n)]
for _ in range(k):
  p,q=map(int,input().split())
  bad[p-1].append(q-1)
  bad[q-1].append(p-1)
  
ans=[0  for _ in range(n)]


for j in range(len(uf.all_group_member())):
  A=uf.all_group_member()[j]
  for h in A:
    ans[h]=j
  
ans1=[]
G=Counter(ans)
for u in range(n):
  F=ans[u]
  C=G[F]
  ch=0
  for T in bad[u]:
    if ans[T]==F:
      ch+=1
  ans1.append(str(C-1-ch-len(good[u])))
  
print(' '.join(ans1))

Submission status: Runtime Error

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.par = [i for i in range(1,n+1)]

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

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

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

N,M,K=map(int,input().split())
U=UnionFind(N)
F=[set() for _ in range(N)]
B=[set() for _ in range(N)]
for _ in range(M):
  a,b=map(int,input().split())
  U.union(a,b)
  F[a-1].add(b)
  F[b-1].add(a)
for _ in range(K):
  a,b=map(int,input().split())
  B[a-1].add(b)
  B[b-1].add(a)
G={}
for i in range(1,N+1):
  x = U.find(i)
  if x in G:
    G[x].add(i)
  else:
    G[x]={i}
ans=[0]*N
for g in G.values():
  for i in g:
    ans[i-1]=len(g-F[i-1]-B[i-1])-1
print(*ans)

Submission status: Runtime Error

Solution code:
N,M,K=map(int,input().split())
G=[]
F=[set([]) for _ in range(N)]
B=[set([]) for _ in range(N)]
for _ in range(M):
  a,b=map(int,input().split())
  F[a-1].add(b)
  F[b-1].add(a)
  p,i=True,0
  for g in G:
    if a in g and b in g:
      i+=1
    elif (a in g or b in g) and p:
      g|={a,b}
      p=False
    elif a in g or b in g:
      G[j]|=g|{a,b}
      G.remove(g)
  if p:
    G.append({a,b})
for _ in range(K):
  a,b=map(int,input().split())
  B[a-1].add(b)
  B[b-1].add(a)
ans=[0]*N
for g in G:
  for i in g:
    ans[i-1]=len(g-F[i-1]-B[i-1]-{i})
print(*ans)

Submission status: Runtime Error

Solution code:
def main():
  N, K = map(int,input().split())
  H = list(map(int,input().split()))
  H.sort(reverse=True)
  print(sum(H[K:]))
  return

main()

Submission status: Runtime Error

Solution code:
from collections import deque, Counter, defaultdict

n, m, k = map(int, input().split())
F = [[] for _ in range(n+1)]
B = [[] for _ in range(n+1)]

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

rks = [0]*(n+1)

def dfs(s,r):
    if rks[s] == 0:
        rks[s] = r
    else:
        return
    for i in F[s]:
        dfs(i,r)

r = 0
for i in range(1,n+1):
    if rks[i] == 0:
        r += 1
        dfs(i,r)

for _ in range(k):
    c, d = map(int, input().split())
    if rks[c] == rks[d]:
        B[c].append(d)
        B[d].append(c)

counter = Counter(rks)
for i in range(1,n+1):
    print(counter[rks[i]] - len(F[i]) - len(B[i]) - 1)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(2*100)

def main():
    
    N, M, K = map(int, input().split())
    G = {v: deque([]) for v in range(N)}
    G_original = {v: deque([]) for v in range(N)}
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
        G_original[a].append(b)
        G_original[b].append(a)

    Block = {v: deque([]) for v in range(N)}
    for _ in range(K):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        Block[c].append(d)
        Block[d].append(c)

    # seen = [0]*(N)
    # stack = []
    color = {v: None for v in range(N)}
    col2v = {col: set() for col in range(N)}
    
    # def dfs(j, col):
    #     if color[j] is not None:
    #         return
    #     # seen[j] = 1
    #     col2v[col] = set()
    #     stack.append(j)
    #     color[j] = col
    #     col2v[col].add(j)
    #     while stack:
    #         s = stack[-1]
    #         if not G[s]:
    #             stack.pop()
    #             continue
    #         g_NO  = G[s].popleft()
    #         if color[g_NO] is not None:
    #             continue
    #         color[g_NO] = col
    #         col2v[col].add(g_NO)
    #         # color[g_NO] = 1
    #         stack.append(g_NO)
    def dfs(node, co):
        if color[node] is not None:
            return
        
        color[node] = co
        col2v[co].add(node)
        for n in G[node]:
            dfs(n, co)
        return
        
    c = 0
    for start in range(N):
        dfs(start, c)
        c += 1
    
    ans = []
    for v in range(N):
        # kouho = col2v[color[v]]
        # # print(kouho)
        # block = Block[v]
        # # print(block)
        # friend = G_original[v]
        # # print(friend)
        # tmp = kouho - set(block + friend)
        ans.append(len(col2v[color[v]] - set(Block[v]+G_original[v]))-1)
        
        # print("##############")
    print(*ans)
main()