Problem:


Score : 400 points

Problem Statement

An SNS has N users - User 1, User 2, \cdots, User N.

Between these N users, there are some relationships - M friendships and K blockships.

For each i = 1, 2, \cdots, M, there is a bidirectional friendship between User A_i and User B_i.

For each i = 1, 2, \cdots, K, there is a bidirectional blockship between User C_i and User D_i.

We define User a to be a friend candidate for User b when all of the following four conditions are satisfied:

a \neq b.

There is not a friendship between User a and User b.

There is not a blockship between User a and User b.

There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a, c_L = b, and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1.

For each user i = 1, 2, ... N, how many friend candidates does it have?

Constraints

All values in input are integers.

2 ≤ N ≤ 10^5

0 \leq M \leq 10^5

0 \leq K \leq 10^5

1 \leq A_i, B_i \leq N

A_i \neq B_i

1 \leq C_i, D_i \leq N

C_i \neq D_i

(A_i, B_i) \neq (A_j, B_j) (i \neq j)

(A_i, B_i) \neq (B_j, A_j)

(C_i, D_i) \neq (C_j, D_j) (i \neq j)

(C_i, D_i) \neq (D_j, C_j)

(A_i, B_i) \neq (C_j, D_j)

(A_i, B_i) \neq (D_j, C_j)

Input

Input is given from Standard Input in the following format:

N M K
A_1 B_1
\vdots
A_M B_M
C_1 D_1
\vdots
C_K D_K

Output

Print the answers in order, with space in between.

Sample Input 1

4 4 1
2 1
1 3
3 2
3 4
4 1

Sample Output 1

0 1 0 1

There is a friendship between User 2 and 3, and between 3 and 4. Also, there is no friendship or blockship between User 2 and 4. Thus, User 4 is a friend candidate for User 2.

However, neither User 1 or 3 is a friend candidate for User 2, so User 2 has one friend candidate.

Sample Input 2

5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5

Sample Output 2

0 0 0 0 0

Everyone is a friend of everyone else and has no friend candidate.

Sample Input 3

10 9 3
10 1
6 7
8 2
2 5
8 4
7 3
10 9
6 4
5 8
2 6
7 5
3 1

Sample Output 3

1 3 5 4 3 3 3 3 1 0



Sample input:
4 4 1
2 1
1 3
3 2
3 4
4 1


Sample output:
0 1 0 1

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.root = list(range(n + 1))
        self.size = [1] * (n + 1)
        
    def Find_Root(self, x):
        if (self.root[x] == x):
            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.size[x] > self.size[y]):
            self.size[x] += self.size[y]
            self.root[y] = x
        else:
            self.size[y] += self.size[x]
            self.root[x] = y
                
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

N, M, K = map(int, input().split())
A = UnionFind(N)
#F = defaultdict(list) 下のように定義しなくとも, リストにない場合でも処理してくれる。
#B = defaultdict(list)
F = [0] * (N + 1) 
B = [0] * (N + 1)
for i in range(M):
    a, b = map(int, input().split())
    F[a] += 1
    F[b] += 1
    A.Unite(a, b)
for i in range(K):
    a, b = map(int, input().split())
    if  A.isSameGroup(a, b):
        B[a] += 1
        B[b] += 1
ans = []
for i in range(1, N + 1):
    size = A.size[A.root[i]]
    friend = F[i]
    block = B[i]
    x = size - friend - block - 1
    ans.append(str(x))
print(" ".join(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
        for g in fg:
            if i in g and f in g:
                flg = True
                continue
            elif not (i in g or f in g):
                continue
            else:
                if i in g:
                    g.add(f)
                else:
                    g.add(i)
                
                flg = True
                break
            
        if not flg:
            fg.append(set([i, f]))

for i in range(len(fg)-1):
    for j in range(i+1, len(fg)):
        if fg[i] & fg[j] != set():
            fg[i] = fg[i] | fg[j]
            fg[j].clear()

#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,))

print(cand)

# 友人候補をカウント
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

line = sys.stdin.readline().strip()
n,m,k = map(int, line.split())
roots = list(range(n))
linked = [0]*n
for i in range(m):
    line = sys.stdin.readline().strip()
    a,b = map(int, line.split())
    c, d = min(a,b)-1, max(a,b) - 1
    linked[c] += 1 
    linked[d] += 1
    while c != roots[c]:
        c = roots[c]
    while d != roots[d]:
        d = roots[d]
    e,f = min(c,d), max(c,d)
    roots[f] = e


for i in range(n):
    cursor = i
    while cursor != roots[cursor]:
        cursor = roots[cursor]
    roots[i] = cursor

print(roots)
res = [0]*n
for i in range(k):
    line = sys.stdin.readline().strip()
    a,b = map(int, line.split())
    c,d = a-1, b-1
    # same group blacklist
    if roots[c] == roots[d]:
        res[c] -= 1
        res[d] -= 1 
set_sizes = dict()

rs = list(set(roots))
for r in rs:
    count = 0
    for one in roots:
        if one == r:
            count += 1
    set_sizes[r] = count

for i in range(n):
    r = roots[i]
    res[i] += (set_sizes[r]-1-linked[i])
print (" ".join(map(str, res)))

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, N):
        self.rank = [0] * N
        self.parent = [i for i in range(N)]
        self.n = N
        self.size = [1 for i in range(N)]
    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 (x == y):
            return
        if (self.rank[x] < self.rank[y]):
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def get_parents(self):
        count = 0
        for i in range(self.n):
            if self.find(i) == i:
                count += 1
        return count
    def get_size(self, x):
        root = self.find(x)
        return self.size[root]
N,M,K = map(int,input().split())
U = UnionFind(N)
direct = [0 for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    U.unite(a,b)
    direct[a] += 1
    direct[b] += 1
neg = [0 for i in range(N)]
for i in range(K):
    c,d = map(int,input().split())
    c,d = c-1,d-1
    if U.same(c,d):
        neg[c] += 1
        neg[d] += 1
ans = []
for i in range(N):
    print(U.get_size(i))
    ans.append(U.get_size(i)-1-neg[i]-direct[i])
print(*ans)

Submission status: Wrong Answer

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

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

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

        if x == y:
            return

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

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

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
def solve():
  n,m,k = (int(i) for i in input().split())
  uff = UnionFind(n)
  ufb = UnionFind(n)
  query = [0]*n
  query2 = []
  for i in range(m):
    a,b = (int(i)-1 for i in input().split())
    uff.union(a,b)
    query[a] += 1
    query[b] += 1
    query2.append((a,b))
  for i in range(k):
    a,b = (int(i)-1 for i in input().split())
    if uff.same(a,b):
      ufb.union(a,b)
    query2.append((a,b))
  for i in range(k+m):
    a,b = query2[i]
    if a>b:
      query2[i] = (b,a)
  tmp = len(query2) -len(list(set(query2)))
  for i in range(n):
    print(uff.size(i)-query[i]-(ufb.size(i)+tmp), end=" ")
solve()

Submission status: Wrong Answer

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

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

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

        if x == y:
            return

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

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

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
def solve():
  n,m,k = (int(i) for i in input().split())
  uff = UnionFind(n)
  ufb = UnionFind(n)
  query = [0]*n
  
  for i in range(m):
    a,b = (int(i)-1 for i in input().split())
    uff.union(a,b)
    query[a] += 1
    query[b] += 1
  for i in range(k):
    a,b = (int(i)-1 for i in input().split())
    if uff.same(a,b):
      ufb.union(a,b)
  for i in range(n):
    print(uff.size(i)-query[i]-(ufb.size(i)), end=" ")
solve()

Submission status: Wrong Answer

Solution code:
class UnionFind:
    """
    素集合データ構造: 要素を素集合（互いに重ならない集合）に分割して管理するデータ構造
        Union: 2つの集合を1つに併合する
        Find: ある要素がどの集合に属しているかを判定する
    """

    def __init__(self, n):
        self.n = n
        # 各要素の親要素の番号を格納するリスト
        # 要素が根（ルート）の場合は[-そのグループの要素数]を格納する
        self.parents = [-1] * n

    def find(self, x):
        """
        要素xが属するグループの根を返す
        """
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """
        要素xが属するグループと要素yが属するグループとを併合する
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

    def size(self, x):
        """
        要素xが属するグループのサイズ（要素数）を返す
        """
        return -self.parents[self.find(x)]

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

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

    def roots(self):
        """
        すべての根の要素をリストで返す
        """
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """
        グループの数を返す
        """
        return len(self.roots())

    def all_group_members(self):
        """
        {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
        """
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        """
        print()での表示用
        """
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


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

uf = UnionFind(n)
friend = [set() for _ in range(n)]
block = [set() for _ in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    friend[a].add(b)
    friend[b].add(a)
    uf.union(a, b)

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

for i in range(n):
    print(uf.size(i) - len(friend[i]) - len(block[i]) - 1, end=' ')

Submission status: Wrong Answer

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())
    
    par=[-1 for _ in range(N)]
    # 負なら根でabsがその根の属する木のサイズ
    # 正ならその値が親

    def root(n):
        if par[n]==n:
            return n
        else:
            par[n]=root(par[n]) # 親の根に繋ぎなおす
            return par[n]
    
    def unite(m,n):
        x=root(m)
        y=root(n)
        if x==y: # 同じ木にいる
            pass
        if par[x]>par[y]: # yのサイズの方が大きい:swap
            x,y=y,x 
        par[x]+=par[y] # サイズの大きいxにくっつける: サイズを記録
        par[y]=x 

    def issame(m,n):
        return root(m)==root(n)
    
    def size(n): # nの属する木のsizeを取得
        return -par[root(n)]
    
    # iの求めたい値 = size(i) -直接の友達関係の数 -iの木上でブロック関係にある数 -1
    # 直接の友達関係ならお互いに同じ木にいる
    ans=[-1 for _ in range(N)] # 自分の分: -1
    
    for _ in range(M): #木達の構築
        A,B=map(int,input().split())
        unite(A-1,B-1)
        # 直接の友達関係を引く
        ans[A-1]-=1
        ans[B-1]-=1
    for _ in range(K): # ブロック関係にあるかどうか
        C,D=map(int,input().split())
        #同じ木でなければ答えに関係ない,同じ木にいるなら引く
        if issame(C-1,D-1):
            ans[C-1]-=1
            ans[D-1]-=1
    for i in range(N): 
        print(ans[i]+size(i))

Submission status: Wrong Answer

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

class UnionFind:
    def __init__(self, val):
        self.parent = self
        self.val = val
        self.rank = 0
        self.size = 1

    def get_root(self):
        n = self
        while n.parent is not n:
            n = n.parent
        return n

    def find_set(self):
        return self.get_root().val


friends = []
for i in range(n + 1):
    friends.append(UnionFind(i))

graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    x, y = friends[a], friends[b]
    x_root, y_root = x.get_root(), y.get_root()
    if x_root.rank == y_root.rank:
        y_root.parent = x_root
        x_root.rank += 1
        x_root.size += y_root.size
    elif x_root.rank > y_root.rank:
        y_root.parent = x_root
        x_root.size += y_root.size
    else:
        x_root.parent = y_root
        y_root.size += x_root.size

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


labels = [None] * (n + 1)
parents = [0] * (n + 1)
for i in range(1, n + 1):
    u = friends[i]
    parents[i] = u.get_root().val
CounterDict = Counter(parents)

for i in range(len(parents)):
    p = parents[i]
    labels[i] = [p, CounterDict.get(p)]

ans = []
for i in range(1, n + 1):
    num = labels[i][1] - 1
    for j in graph[i]:
        if labels[i][0] == labels[j][0]:
            num -= 1
    for k in block[i]:
        if labels[i][0] == labels[k][0]:
            num -= 1
    ans.append(num)

print(labels)

Submission status: Wrong Answer

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 parents[C-1] == parents[D-1]:
		a[C-1] -= 1
		a[D-1] -= 1
print(*a)

Submission status: Wrong Answer

Solution code:
N, M, K = map(int, input().split())
ans = [0] * N
fri = [[] for i in range(N)]
blo = [[] for i in range(N)]
for i in range(M):
  a,b = map(int, input().split())
  fri[a-1].append(b-1)
  fri[b-1].append(a-1)
for i in range(K):
  c,d = map(int, input().split())
  blo[c-1].append(d-1)
  blo[d-1].append(c-1)
zumi = []
before = 0
for i in range(N):
  if i not in zumi:
    zumi.append(i)
    que = fri[i]
    after = before + len(fri[i])
    while que:
      tmp = que.pop()
      zumi.append(tmp)
      for x in fri[tmp]:
        if (x not in zumi) and (x not in que):
          que.append(x)
          after += 1
    for i in range(before, after+1):
      ans[zumi[i]] = after - before - len(fri[i])
    before = after + 1
  else:
    continue
print(*ans)

Submission status: Wrong Answer

Solution code:
N, M, K = map(int, input().split())
ans = [0] * N
fri = [[] for i in range(N)]
blo = [[] for i in range(N)]
for i in range(M):
  a,b = map(int, input().split())
  fri[a-1].append(b-1)
  fri[b-1].append(a-1)
for i in range(K):
  c,d = map(int, input().split())
  blo[c-1].append(d-1)
  blo[d-1].append(c-1)
zumi = []
before = 0
for i in range(N):
  if i not in zumi:
    zumi.append(i)
    que = fri[i]
    after = before + len(fri[i])
    while que:
      tmp = que.pop()
      zumi.append(tmp)
      for x in fri[tmp]:
        if (x not in zumi) and (x not in que):
          que.append(x)
          after += 1
    for i in range(before, after+1):
      ans[zumi[i]] = after - before - len(fri[i])
    for j in range(before, after):
      for k in range(j+1, after + 1):
        if zumi[k] in blo[zumi[j]]:
          ans[zumi[k]] -= 1
          ans[zumi[j]] -= 1
    before = after + 1
  else:
    continue
print(*ans)

Submission status: Wrong Answer

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

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

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

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

def dfs(graph, start):
    visited = set([start])
    stack = []
    can_reach = set([start])
    for f in graph[start]:
        stack.append(f)
        can_reach.add(f)
    while stack:
        friend = stack.pop()
        visited.add(friend)
        candidates = graph[friend]
        for c in candidates:
            if c not in visited:
                can_reach.add(c)
                stack.append(c)
    return can_reach

labels = [None] * (n + 1)
for i in range(1, n + 1):
    if labels[i] is None:
        c = dfs(graph, i)
        for j in c:
            labels[j] = [i, len(c)]

ans = []
for i in range(1, n + 1):
    num = labels[i][1] - 1
    for j in graph[i]:
        if labels[i][0] == labels[j][0]:
            num -= 1
    for k in block[i]:
        if labels[i][0] == labels[k][0]:
            num -= 1
    ans.append(num)
print(labels)

Submission status: Wrong Answer

Solution code:
import sys
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: Wrong Answer

Solution code:
from collections import defaultdict
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: Wrong Answer

Solution code:
from collections import defaultdict
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self._size = [1]*(n+1)

    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 = defaultdict(set)

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

blocks = defaultdict(set)

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



res = []

for i in range(N):
    n = uni.size(i)-1
    for f in friends[i]:
        if uni.same_check(i, f):
            n-=1

    for f in blocks[i]:
        if uni.same_check(i, f):
            n-=1


    res.append(n)

print_l(res)

Submission status: Wrong Answer

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(list(map(str,r))))

Submission status: Wrong Answer

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(r)

Submission status: Wrong Answer

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(m)]
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: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
 
n,m,k = map(int,input().split())
ab = [set() for _ in range(n)]
cd = [[] * n for _ in range(n)]
print(cd)

 
#Union Find
 
#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True
 
#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]
 
#初期化
#根なら-size,子なら親の頂点
par = [-1]*n

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

for i in range(k):
    c, d = [int(x) for x in input().split()]
    if same(c - 1, d - 1):
        cd[c - 1].append(d - 1)
        cd[d - 1].append(c - 1)

ans = [0] * n

for i in range(n):
    ans[i] = size(i) - 1 - len(cd[i]) - len(ab[i])

print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

N, M, K = map(int, input().split())
friend_relationships = []
blocked_relationships = []
adjecency_list = [[i] for i in range(N)]
list_of_candidates_num = []

for i in range(M):
    l = list(map(int, input().split()))
    friend_relationships.append(l)

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

for relationship in friend_relationships:
    adjecency_list[relationship[0]-1].append(relationship[1]-1)
    adjecency_list[relationship[1]-1].append(relationship[0]-1)

def breadth_first_search(input_adjecency_list):
    num_of_nodes = len(input_adjecency_list)
    work_queue = deque([])
    will_visit = set(list(range(num_of_nodes)))
    visiting = set()
    visited = set()
    output_list = [[] for i in range(num_of_nodes)]

    while will_visit:
        s = will_visit.pop()
        work_queue.append(s)

        while work_queue:
            here = work_queue.popleft()

            if here in visited: continue

            for node in input_adjecency_list[here]:
                work_queue.append(node)
                visiting.add(node)
                visited.add(here)

        for i in list(visiting):
            output_list[i]= set(list(visiting))

        visiting.clear()
        will_visit = will_visit - visited

    return output_list

def candidates_choice(input_graph, input_friends, input_blocked):
    num_of_nodes = len(input_graph)
    output_graph = input_graph

    for relationship in input_friends:
        output_graph[relationship[0]-1].discard(relationship[1]-1)
        output_graph[relationship[1]-1].discard(relationship[0]-1)

    for relationship in input_blocked:
        output_graph[relationship[0]-1].discard(relationship[1]-1)
        output_graph[relationship[1]-1].discard(relationship[0]-1)

    for self_node in range(num_of_nodes):
        output_graph[self_node].discard(self_node)

    return output_graph

graph = breadth_first_search(adjecency_list)
candidates_graph = candidates_choice(graph, friend_relationships, blocked_relationships)
for i in range(N):
    list_of_candidates_num.append(len(candidates_graph[i]))

"""
print(adjecency_list)
print(graph)
print(candidates_graph)
"""

print(list_of_candidates_num)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
 
n,m,k = map(int,input().split())
ab = [set() for _ in range(n)]
cd = [set() for _ in range(n)]

 
#Union Find
 
#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True
 
#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]
 
#初期化
#根なら-size,子なら親の頂点
par = [-1]*n

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

for i in range(k):
    c, d = [int(x) for x in input().split()]
    cd[c - 1].add(d - 1)
    cd[d - 1].add(c - 1)

ans = [0] * n

for i in range(n):
    ans[i] = size(i) - 1 - len(cd[i]) - len(ab[i])

print(*ans)