Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

a \neq b.

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

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

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

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

Constraints

All values in input are integers.

2 ≤ N ≤ 10^5

0 \leq M \leq 10^5

0 \leq K \leq 10^5

1 \leq A_i, B_i \leq N

A_i \neq B_i

1 \leq C_i, D_i \leq N

C_i \neq D_i

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

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

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

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

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

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

Input

Input is given from Standard Input in the following format:

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

Output

Print the answers in order, with space in between.

Sample Input 1

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

Sample Output 1

0 1 0 1

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

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

Sample Input 2

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

Sample Output 2

0 0 0 0 0

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

Sample Input 3

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

Sample Output 3

1 3 5 4 3 3 3 3 1 0



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


Sample output:
0 1 0 1

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(100000000)
n,m,k = [int(v) for v in input().split()]

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

for _ in range(m):
    l,r = [int(v) for v in input().split()]
    friend[l].append(r)
    friend[r].append(l)

for _ in range(k):
    l,r = [int(v) for v in input().split()]
    block[l].append(r)
    block[r].append(l)

comb = [{"g":-1,"sum":0} for _ in range(n+1)]
visited = [False for _ in range(n+1)]

def dfs(node,depth,g):
    if visited[node]:
        return depth - 1
    visited[node] = True
    for next_node in friend[node]:
        depth = dfs(next_node,depth+1,g)
    comb[node] = {
            "g":g,
            "sum":max(comb[node]["sum"],depth)
            }
    return depth

g = 0
for i in range(n):
    dfs(i+1,1,g)
    g += 1

for i in range(n):
    ans = comb[i+1]["sum"] - 1 - len(friend[i+1])
    for to in block[i+1]:
        if comb[i+1]["g"] == comb[to]["g"]:
            ans -= 1

    print(ans,end=' ')

Submission status: Wrong Answer

Solution code:
n, m, k = map(int, input().split())
friends = []
graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    friends.append((a - 1, b - 1))
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)

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

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

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

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


unions = []
for i in range(n):
    unions.append(Union(i))

for a, b in friends:
    x, y = unions[a], unions[b]
    if x.find_set() == y.find_set():
        continue
    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
    elif x_root.rank > y_root.rank:
        y_root.parent = x_root
    else:
        x_root.parent = y_root
    size = x_root.size + y_root.size
    x_root.size = size
    y_root.size = size

d = {}
relation = []
for i in range(n):
    u = unions[i]
    parent = u.find_set()
    relation.append((parent, u.parent.size))
    if parent in d:
        d[parent].add(i)
    else:
        d[parent] = set([i])

ans = []
for i in range(n):
    t = relation[i][1] - 1
    parent = relation[i][0]
    chain = d.get(parent, set())
    for j in graph[i]:
        if j in chain:
            t -= 1
    for k in block[i]:
        if k in chain:
            t -= 1
    ans.append(t)

print(*ans)

Submission status: Wrong Answer

Solution code:
n, m, k = map(int, input().split())
friends = []
friend_num = [0] * n
for _ in range(m):
    a, b = map(int, input().split())
    friends.append((a - 1, b - 1))
    friend_num[a - 1] += 1
    friend_num[b - 1] += 1

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

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

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

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


unions = []
for i in range(n):
    unions.append(Union(i))

for a, b in friends:
    x, y = unions[a], unions[b]
    if x.find_set() == y.find_set():
        continue
    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
    elif x_root.rank > y_root.rank:
        y_root.parent = x_root
    else:
        x_root.parent = y_root
    size = x_root.size + y_root.size
    x_root.size = size
    y_root.size = size

d = {}
relation = []
for i in range(n):
    u = unions[i]
    val = u.find_set()
    relation.append((val, u.parent.size))
    if val in d:
        d[val].add(i)
    else:
        d[val] = set([i])

ans = []
for i in range(n):
    t = relation[i][1] - 1 - friend_num[i]
    val = relation[i][0]
    chain = d.get(val, set())
    for j in block[i]:
        if j in chain:
            t -= 1
    ans.append(t)

print(*ans)

Submission status: Wrong Answer

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


class UnionFind(object):
    def __init__(self, n):
        self.parent={i:i for i in range(1,n+1)}
        self.size={i:1 for i in range(1,n+1)}
    def find(self, a):
        if self.parent[a]!=a:
            self.parent[a]=self.find(self.parent[a])
        return self.parent[a]
    def getsize(self, a):
        return self.size[self.find(a)]
    def unite(self, a, b):
        a=self.find(a)
        b=self.find(b)
        if a==b:return
        if self.size[a]>self.size[b]:
            self.size[a]+=self.size[b]
            self.parent[b]=a
        else:
            self.size[b]+=self.size[a]
            self.parent[a]=b
    def isunited(self, a, b):
        return self.find(a)==self.find(b)


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

    d = {i:set() for i in range(1, N+1)}
    block = {i:set() for i in range(1, N+1)}
    candidate = {i:set() for i in range(1, N+1)}

    uft = UnionFind(N)

    for _ in range(M):
        A, B = map(int, input().split())
        d[A].add(B)
        d[B].add(A)
        uft.unite(A, B)

    for _ in range(K):
        C, D = map(int, input().split())
        block[C].add(D)
        block[D].add(C)

    for i in range(1, N+1):
        cd = [j for j in range(i+1, N) if not j in d[i] and not j in candidate[i]]
        for j in cd:
            if uft.isunited(i, j) and not j in block[i]:
                candidate[i].add(j)
                candidate[j].add(i)

    print(*map(len, candidate.values()))


if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
used = [];
w = [];

def dfs(v, num):
    used[v] = num;
    for x in w[v]:
        if used[x] == 0:
            dfs(x, num);


n, m, k = (int(i) for i in input().split());

for i in range(n):
    w.append([]);

for j in range(m):
    u, v = (int(i) for i in input().split());
    u -= 1;
    v -= 1;
    w[u].append(v);
    w[v].append(u);

block = [];
for j in range(k):
    u, v = (int(i) for i in input().split());
    u -= 1;
    v -= 1;
    block.append([u, v]);

for i in range(n):
    used.append(0);

# cnt_comp = 0;
# for i in range(n):
#     if used[i] == 0:
#         cnt_comp += 1;
#         dfs(i, cnt_comp);

# cnt = [0 for i in range(cnt_comp)];
#
# for i in range(n):
#     cnt[used[i] - 1] += 1;
#
# res = [0 for i in range(n)];
# for i in range(n):
#     res[i] = cnt[used[i] - 1] - 1;
# #print(res);
# for x in block:
#     if used[x[0]] == used[x[1]]:
#         res[x[0]] -= 1;
#         res[x[1]] -= 1;
# #print(res);
# for i in range(n):
#     for v in w[i]:
#         if used[v] == used[i]:
#             res[i] -= 1;
# 
# #print(cnt);
#
# for i in res:
#     print(i, end=" ");

Submission status: Wrong Answer

Solution code:
def dfs(graph, start):
    visited = set([start])
    stack = [start]

    while stack:
        v = stack.pop()
        for w in graph[v]:
            if w not in visited:
                stack.append(w)
                visited.add(w)
                break
        yield v


def read_graph(nodes, edges):
    graph = [[] for _ in range(nodes)]
    for _ in range(edges):
        a, b = (int(x) - 1 for x in input().split())
        graph[a].append(b)
        graph[b].append(a)

    return graph


def count_candidates(n, counts, groups, block, friend):
    for i in range(n):
        count = counts[groups[i]]
        for v in block[i]:
            if groups[i] == groups[v]:
                count -= 1

        count -= len(friend[i])
        count -= 1
        yield count


def main():
    n, m, k = map(int, input().split())
    friend = read_graph(n, m)
    block = read_graph(n, k)

    groups = [-1 for _ in range(n)]
    counts = []
    i = 0
    group_id = 0
    while i < n:
        if groups[i] != -1:
            i += 1
            continue

        for j, v in enumerate(dfs(friend, i)):
            groups[v] = group_id

        counts.append(j + 1)
        group_id += 1

    print(" ".join(str(i) for i in count_candidates(n, counts, groups, block, friend)))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
class UnionFind:
  def __init__(self, n):
    self.parents = list(range(n))
    self.ranks = [0] * n

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

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

  def unite(self, x, y):
    x = self.root(x)
    y = self.root(y)
    if x == y:
      return
    if self.ranks[x] < self.ranks[y]:
      self.parents[x] = y
    else:
      self.parents[y] = x
      if self.ranks[x] == self.ranks[y]:
        self.ranks[x] += 1

n, m, k = map(int, input().split())
u = UnionFind(n)
allusers = {i for i in range(n)}
users = [set() for _ in range(n)]
for _ in range(m):
  a, b = map(int, input().split())
  users[a - 1].add(b - 1)
  users[b - 1].add(a - 1)
  u.unite(a - 1, b - 1)
for _ in range(k):
  a, b = map(int, input().split())
  users[a - 1].add(b - 1)
  users[b - 1].add(a - 1)

print(0)

Submission status: Wrong Answer

Solution code:
n, m, k = map(int, input().split())
users = [set() for _ in range(n)]
for _ in range(m):
  a, b = map(int, input().split())
  users[a - 1].add(b - 1)
  users[b - 1].add(a - 1)
for _ in range(k):
  a, b = map(int, input().split())
  users[a - 1].add(b - 1)
  users[b - 1].add(a - 1)

print(*(n - len(user) - 1 for user in users))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# Union Find


class UnionFind(object):
    def __init__(self, n: int):
        """ ノードのつながりを辞書型で表現する
        要素数nであり、要素は0からn-1である想定
        >> - usage
        g = Graph(n=n)

        """
        self.adjacency_dict = {}
        self.parent = [None] * n

        for i in range(n):
            self.add_vertex(i)
            self.parent[i] = i
        self.rank = [0] * n

    def add_vertex(self, v: int):
        """ ノードを追加する """
        self.adjacency_dict[v] = []

    def unite(self, v1: int, v2: int):
        """ ノード同士をつなぐ。"""
        if v1 == v2:
            return

        # すでにつながっている場合は親の更新のみしておく
        if self.same(v1, v2):
            return

        p1 = self.parent[v1]
        p2 = self.parent[v2]

        # つながっていない場合は親同士をつなげる
        # その場合rankが小さい方から大きい方につなげる
        if self.rank[p1] == self.rank[p2]:
            self.update(p1, p2)
            self.rank[p2] += 1
        elif self.rank[p1] < self.rank[p2]:
            self.update(p1, p2)
        else:
            self.update(p2, p1)

    def update(self, v, parent):
        self.adjacency_dict[v].append(parent)

    def same(self, v1, v2):
        """ 親が同一であれば連結 """
        self.parent[v1] = self.root(v1)
        self.parent[v2] = self.root(v2)

        return self.parent[v1] == self.parent[v2]

    def root(self, v1):
        """ vから上向きに辿って根を調べる """
        if self.adjacency_dict[v1] == []:
            return v1

        for v in self.adjacency_dict[v1]:
            parent = self.root(v)
        return parent

    def print_graph(self):
        print(self.adjacency_dict)




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


class UnionFindFriend(UnionFind):
    def __init__(self, n):
        super(UnionFindFriend, self).__init__(n)
        self.friends = {}
        self.blocks = {}

        for i in range(n):
            self.friends[i] = []
            self.blocks[i] = []

    def add_friends(self, v1, v2):
        self.friends[v1].append(v2)
        self.friends[v2].append(v1)

    def add_blocks(self, v1, v2):
        self.blocks[v1].append(v2)
        self.blocks[v2].append(v1)


def get_next():
    c1, c2 = map(int, input().split())
    c1, c2 = c1 - 1, c2 -1
    return c1, c2


uf = UnionFindFriend(N)

for i in range(M):
    c1, c2 = get_next()
    uf.unite(c1, c2)
    uf.add_friends(c1, c2)

for i in range(K):
    c1, c2 = get_next()
    uf.add_blocks(c1, c2)

# 全ての要素のroot（つまり自分がどのグループに所属するか）を格納
roots = [uf.root(i) for i in range(N)]
print(roots)
res = {}

# rootsからグループのリストを取得し、一つずつ処理する
for root in list(set(roots)):
    idxes = [idx for idx, element in enumerate(roots) if element == root]
    len_idxes = len(idxes)
    print(root, idxes)

    for idx in idxes:
        # 友達候補 = [連携成分の数 -1] - [友達の数] - [連結成分におけるブロック数]
        result = len_idxes - 1 - len(uf.friends[idx]) - len(set(uf.blocks[idx]) & set(idxes))
        res[idx] = result

for i in range(N):
    print(res[i], end=' ')

Submission status: Wrong Answer

Solution code:
N,M,K = map(int, input().split())
A = []
relate=[]
t_1 = []
for o in range(N):
    t_2=[]
    for p in range(N):
        t_2.append(0)
    relate.append(t_2)
for i in range(M+K):
    t_1 = list(map(int, input().split()))
    A.append(t_1)
for j in range(M+K):
    if A[j][0] != A[j][1]:
        relate[A[j][0]-1][A[j][1]-1] = 1
        relate[A[j][1]-1][A[j][0]-1] = 1

for u in range(N):
    count_1=0
    for y in range(N):
        if relate[u][y]==1:
            count_1+=1
    print(N-1-count_1,end=" ")

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
def bfs(G, start):
    queue = deque()
    visited = [False] * (len(G))
    queue.append(start)
    while queue:
        target = queue.popleft()
        for j in G[target]:
            if visited[j] == False:
                visited[j] = True
                queue.append(j)
    visited = [k for k, x in enumerate(visited) if x ]
    return set(visited)

def main():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    F_G = [[] for _ in range(N)]
    B_G = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        F_G[a-1].append(b-1)
        F_G[b-1].append(a-1)
    for _ in range(K):
        c, d = map(int, input().split())
        B_G[c-1].append(d-1)
        B_G[d-1].append(c-1)
    sub = list(range(N))
    for i in sub:
        can = list(range(N))
        can = set(can)
        can -= set(B_G[i]) # ブロック関係にある人を友達候補から削除
        can -= set(F_G[i]) # 友達関係に既にある人を友達候補から削除
        v = bfs(F_G, i)    # 友達グラフ上でつながっている友達をsetで取得
        can &= v           # 今の候補と積集合とって完成
        if i != N-1:
            print(len(can)-1, end=" ")
        else:
            print(len(can)-1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m,k=map(int,input().split())
link=[[] for _ in range(n)]
block=[[]  for _ in range(n)]
ans=[0]*n
s=[]
for i in range(m):
    a,b=map(int,input().split())
    link[a-1].append(b-1)
    link[b-1].append(a-1)
for i in range(k):
  a,b=map(int,input().split())
  block[a-1].append(b-1)
  block[b-1].append(a-1)
for i in range(n):#スタートの選び方
    u=[0]*n
    q=deque([i])
    while len(q)>0:
        x=q.pop()
        u[x]=1
        for j in link[x]:
            if u[j]==1:
              continue
            elif j in q:
              continue
            else:q.append(j)
    s.append(u)
    ans[i]=sum(u)-1

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np
n,m,k=map(int,input().split())
link=[[] for _ in range(n)]
block=[[]  for _ in range(n)]
ans=[]
s=[]
for i in range(m):
    a,b=map(int,input().split())
    link[a-1].append(b-1)
    link[b-1].append(a-1)
for i in range(k):
  a,b=map(int,input().split())
  block[a-1].append(b-1)
  block[b-1].append(a-1)
for i in range(n):#スタートの選び方
    visited=set()
    q=deque([i])
    while len(q)>0:
        x=q.pop()
        visited.add(x)
        for j in link[x]:
            if j in visited:
              continue
            elif j in q:
              continue
            else:q.append(j)
    ans.append(len(visited))
    s.append(visited)

Submission status: Wrong Answer

Solution code:
import sys
N, M, K = map(int, sys.stdin.readline().split())
setList = [set(list(map(int, sys.stdin.readline().split()))) for _ in range(M+K)]
li = []
i = 1
for s in setList:
  j = 2
  while i < N:
    while j <= N:
      if s != {i, j}:
        li.append(i)
        li.append(j)
      j += 1
    i += 1
n = 1
while n <= N:
  print(li.count(n), end="")
  n += 1

Submission status: Wrong Answer

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


class UnionFindLabel(UnionFind):
    def __init__(self, labels):
        assert len(labels) == len(set(labels))

        self.n = len(labels)
        self.parents = [-1] * self.n
        self.d = {x: i for i, x in enumerate(labels)}
        self.d_inv = {i: x for i, x in enumerate(labels)}

    def find_label(self, x):
        return self.d_inv[super().find(self.d[x])]

    def union(self, x, y):
        super().union(self.d[x], self.d[y])

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

    def same(self, x, y):
        return super().same(self.d[x], self.d[y])

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

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

def MAP(): return map(int, input().split())
def ZIP(n): return zip(*(MAP() for _ in range(n)))

N, M, K = list(map(int, input().split()))
ans = [-1] * N
uf = UnionFindLabel(range(1, N + 1))
for i in range(M):
    node1, node2 = list(map(int, input().split()))
    ans[node1 - 1] -= 1
    ans[node2 - 1] -= 1
    if not uf.same(node1, node2):
        uf.union(node1, node2)
for i in range(N):
    ans[i] += uf.size(i + 1)
for i in range(K):
    node1, node2 = list(map(int, input().split()))
    ans[node1 - 1] -= 1
    ans[node2 - 1] -= 1
print(*ans)

Submission status: Wrong Answer

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


class UnionFindLabel(UnionFind):
    def __init__(self, labels):
        assert len(labels) == len(set(labels))

        self.n = len(labels)
        self.parents = [-1] * self.n
        self.d = {x: i for i, x in enumerate(labels)}
        self.d_inv = {i: x for i, x in enumerate(labels)}

    def find_label(self, x):
        return self.d_inv[super().find(self.d[x])]

    def union(self, x, y):
        super().union(self.d[x], self.d[y])

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

    def same(self, x, y):
        return super().same(self.d[x], self.d[y])

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

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

def MAP(): return map(int, input().split())
def ZIP(n): return zip(*(MAP() for _ in range(n)))

N, M, K = list(map(int, input().split()))
ans = [-1] * N
uf = UnionFindLabel(range(1, N + 1))
for i in range(M):
    node1, node2 = list(map(int, input().split()))
    uf.union(node1, node2)
    ans[node1 - 1] -= 1
    ans[node2 - 1] -= 1
for i in range(N):
    ans[i] += uf.size(i + 1)
for i in range(K):
    node1, node2 = list(map(int, input().split()))
    ans[node1 - 1] -= 1
    ans[node2 - 1] -= 1
print(*ans)

Submission status: Wrong Answer

Solution code:
n, m, k = map(int, input().split())
ab = []
c = []
d = []
for i in range(m):
    line = list(map(int, input().split()))
    ab.append([min(line), max(line)])
for i in range(k):
    line = list(map(int, input().split()))
    c.append(line[0])
    d.append(line[1])

def add_dic(p):
    if not p in d_dic:
        d_dic[p] = 1
    else:
        d_dic[p] += 1

d_dic = {}
for i in range(m):
    add_dic(ab[i][0])
    add_dic(ab[i][1])

connection_set_dic = {}
now = 0
for i in range(m):
    flag = 0
    for j in range(now):
        if ab[i][0] in connection_set_dic[j]:
            connection_set_dic[j].add(ab[i][1])
            flag = 1
        if ab[i][1] in connection_set_dic[j]:
            connection_set_dic[j].add(ab[i][0])
            flag = 1
    if flag == 0:
        connection_set_dic[now] = set(ab[i])
        now += 1


for i in range(n):
    connectable = []
    for j in range(len(connection_set_dic)):
        if i in connection_set_dic[j]:
            connectable.append(j)
    if len(connectable) > 1:
        for i in range(1, len(connectable)):
            connection_set_dic[connectable[0]] = connection_set_dic[connectable[0]] | connection_set_dic.pop(connectable[i])

l = len(connection_set_dic)

for i in range(k):
    for j in range(l):
        if c[i] in connection_set_dic[j] and d[i] in connection_set_dic[j]:
            d_dic[c[i]] += 1
            d_dic[d[i]] += 1

for i in range(1,n+1):
    for j in range(l):
        if i in connection_set_dic[j]:
            print(len(connection_set_dic[j]) - d_dic[i] - 1)
            continue

Submission status: Wrong Answer

Solution code:
n,m,k = map(int,input().split())
non_candidate = [1]*n
graph = [[0 for i in range(n)]for j in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    graph[a-1][b-1] = 1
    graph[b-1][a-1] = 1
    non_candidate[a-1] += 1
    non_candidate[b-1] += 1
    
for i in range(k):
    a,b = map(int,input().split())
    non_candidate[a-1] += 1
    non_candidate[b-1] += 1


def dfs (visited ,initial ,graph ):
    global count
    visited[initial] = 1
    for i in range(len(graph)):
        if graph[initial][i] == 1:
            if visited[i] == 0:
                visited[i] =1
                count += 1
                dfs(visited , i, graph)
    return count


ans = [0]*n
for i in range(len(ans)):
    count = 1
    visited = [0]*n
    dfs(visited ,  i, graph)
    ans[i] = count - non_candidate[i]
    
print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
 
N,M,K = list(map(int,input().split()))
ab = [list(map(int,input().split())) for _ in range(M)]
cd = [list(map(int,input().split())) for _ in range(K)]

def links(xx, base=None):
  dif = 0
  if base == None:
    base = [0<<(N-1)]*N
    for x,y in xx:
      base[x-1] = base[x-1] | (1<<(y-1))
      base[y-1] = base[y-1] | (1<<(x-1))
  else:
    for x,y in xx:
      if base[x-1] != base[y-1]:
        base[x-1] = base[x-1] | base[y-1]
        base[y-1] = base[x-1]
        dif = 1
  return base, dif

def link_add(xx, base=None):
  global root, dif
  if base == None:
    root, dif = links(xx)
    root, dif = links(xx,root)
  while dif == 1:
    root, dif = links(xx,root)
  
  return root

def cnt(xx):
  root = link_add(ab)
  base, dif = links(ab+cd)
  ans = [0]*N
  for p in range(N):
    root[p] = root[p] | base[p]
    root[p] = root[p] ^ base[p]
    ans[p] = bin(root[p]).count('1') - 1
  return ans


def prnt(ans):
  for p in range(N):
    print(bin(ans[p]))
  
ans = cnt(ab)
print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
 
N,M,K = list(map(int,input().split()))
ab = [list(map(int,input().split())) for _ in range(M)]
cd = [list(map(int,input().split())) for _ in range(K)]

def links(xx, f):
  for x,y in xx:
      f[x-1] = f[x-1] | (1<<(y-1))
      f[y-1] = f[y-1] | (1<<(x-1))
  return f

def link_add(ans, q=0):
  r = 0
  for p,bit in enumerate(ans):
    for i in range(N):
      if bit & (1<<i):
        ans[p] = ans[p] | ans[i]
        r += 1
  if q != r:
    ans = link_add(ans, r)
  return ans
    

def cnt(p,bit):
  a = -1
  for i in range(N):
    if bit & (1<<i):
      a += 1
  return a

def prnt(f):
  for p in range(N):
    print(bin(f[p]))

f = [0<<(N-1)]*N
fb = [0<<(N-1)]*N
f = links(ab,f)
fb = links(ab + cd,fb)

ans = link_add(f)

for p in range(N):
  ans[p] = ans[p] | fb[p]
  ans[p] = ans[p] ^ fb[p]
  ans[p] = cnt(p,ans[p])

print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)

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

ab = [[] for j in range(n)]
cd = [[] for j in range(n)]

for i in range(m):
    a,b = map(int,input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
    
for i in range(k):
    c,d = map(int,input().split())
    cd[c-1].append(d-1)
    cd[d-1].append(c-1)
    
check = [-1]*n

def dfs(x,check):
    #if check[x] != -1:
    #    return
    for i in range(len(ab[x])):
        cho = ab[x][i]
        #print(cho,x)
        if check[cho] != -1:
            continue
        check[cho] = num
        dfs(cho,check)
    
    return

num = 0
for i in range(n):
    #print(i,check[i])
    if check[i] != -1:
        continue
    dfs(i,check)
    num += 1
#print(check)
exit()
grp_num = max(check)
grp_size = [0]*(grp_num+1)

for i in range(n):
    grp_size[check[i]] += 1
    
for i in range(n):
    hiku = 0
    for j in range(len(cd[i])):
        #print(cd[i],check[i],cd[i][j],check[cd[i][j]])
        if check[cd[i][j]] == check[i]:
            hiku += 1
            #print(hiku,hiku,hiku,hiku,hiku)
    print(grp_size[check[i]]-len(ab[i])-hiku-1,end=' ')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
 
N,M,K = list(map(int,input().split()))
ab = [list(map(int,input().split())) for _ in range(M)]
cd = [list(map(int,input().split())) for _ in range(K)]

def links(xx, f):
  for x,y in xx:
    if x != y:
      f[x-1] = f[x-1] | (1<<(y-1))
      f[y-1] = f[y-1] | (1<<(x-1))
  return f

def link_add(ans):
  c = 0
  for p,bit in enumerate(ans):
    for i in range(N):
      if p == i:next
      if bit & (1<<i):
        ans[p] = ans[p] | ans[i]
        c += 1
  if c == 0:return -1,ans
  return 1,ans

def cnt(p,bit):
  a = -1
  for i in range(N):
    if i == p:next
    if bit & (1<<i):
      a += 1
  return a

f = [0<<(N-1)]*N
fb = [0<<(N-1)]*N
f = links(ab,f)
fb = links(ab + cd,fb)

c,ans = link_add(f)
c = 0
while c == 0:
  c,ans = link_add(ans)

for p in range(N):
  #print(bin(ans[p]),bin(fb[p]))
  ans[p] = ans[p] | fb[p]
  #print(bin(ans[p]))
  ans[p] = ans[p] ^ fb[p]
  #print(bin(ans[p]))
  ans[p] = cnt(p,ans[p])
      
print(*ans)

Submission status: Wrong Answer

Solution code:
class UnionFind:
	def __init__ (self, n):
		self.n = n
		self.parent = [i for i in range(n)]
		self.rank = [1] * n
		self.size = [1] * 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:
			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 is_same(self, x, y):
		return self.find(x) == self.find(y)

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

N, M, K = map(int, input().split())
A, B = [0] * M, [0] * M
C, D = [0] * K, [0] * K

direct = [[] for _ in range(N)]
uf = UnionFind(N)

for i in range(M):
	A[i], B[i] = map(int, input().split())
	A[i] -= 1
	B[i] -= 1
	direct[A[i]].append(B[i])
	direct[B[i]].append(A[i])
	uf.unite(A[i], B[i])

for i in range(K):
	C[i], D[i] = map(int, input().split())
	C[i] -= 1
	D[i] -= 1
	direct[C[i]].append(D[i])
	direct[D[i]].append(C[i])

ans = [0] * N
for i in range(N):
	ans[i] = uf.group_size(i) - len(direct[i]) -1
print(*ans)