Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

a \neq b.

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

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

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

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

Constraints

All values in input are integers.

2 ≤ N ≤ 10^5

0 \leq M \leq 10^5

0 \leq K \leq 10^5

1 \leq A_i, B_i \leq N

A_i \neq B_i

1 \leq C_i, D_i \leq N

C_i \neq D_i

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

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

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

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

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

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

Input

Input is given from Standard Input in the following format:

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

Output

Print the answers in order, with space in between.

Sample Input 1

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

Sample Output 1

0 1 0 1

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

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

Sample Input 2

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

Sample Output 2

0 0 0 0 0

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

Sample Input 3

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

Sample Output 3

1 3 5 4 3 3 3 3 1 0



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


Sample output:
0 1 0 1

Submission status: Runtime Error

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

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

w = [[] for i in range(n)]

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

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

    while stack:
        v = stack[-1]
        for w in graph[v]:
            if w not in visited:
                break

        if w in visited:
            stack.pop()
            yield v
        else:
            stack.append(w)
            visited.add(w)


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

Solution code:
# 同じ木に属する(==そこまでたどりつけるかどうか）の判定にunionfind
# 同じ木に属しているノードはあとで数えることができる（そうだね）
# 除外するやつが出てくる。直の友達+ブロック関係にあるやつ（と自分）
# 同じ木に属しているノードの総数 - (直の友達+ブロック関係+自分自身)が答え
n, m, k = map(int, input().split())
par = [i for i in range(n)]
ans = [0 for _ in range(n)]


def root(x):
    if x == par[x]:
        return x
    y = root(par[x])
    par[x] = y
    return y


def union(x, y):
    if x > y:
        x, y = y, x
    rx, ry = root(x), root(y)
    if rx != ry:
        par[ry] = rx


friends = [[] for _ in range(n)]
blocks = [[] for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    union(a - 1, b - 1)
    friends[a - 1].append(b - 1)
    friends[b - 1].append(a - 1)
for _ in range(k):
    c, d = map(int, input().split())
    blocks[c - 1].append(d - 1)
    blocks[d - 1].append(c - 1)

# 木に属しているやつを数えるぜ
group_count = [0 for _ in range(n)]
for i in range(n):
    group_count[root(i)] += 1
# 答えを作るぜ
for i in range(n):
    # 初期化（じゃないけど）
    ans[i] += group_count[root(i)]
    # 直の友達を除く
    ans[i] -= len(friends[i])
    # ブロックしてるやつを除く
    for b in blocks[i]:
        ra, rb = root(i), root(b)
        if ra == rb:
            ans[i] -= 1
    # 自分自身を除く
    ans[i] -= 1
print(" ".join(list(map(str, ans))))

Submission status: Runtime Error

Solution code:
#https://www.slideshare.net/chokudai/union-find-49066733
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.ranks = [0] * self.n
    self.parents = list(range(self.n))

  def find(self, x):
    if self.parents[x] == x:
      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.ranks[x] > self.ranks[y]:
      x, y = y, x
    if self.ranks[x] == self.ranks[y]:
      self.ranks[x] += 1

    self.parents[y] = x
        
  def issame(self, x, y):
    return self.find(x) == self.find(y)
  
  def get_root_members(self):
    roots = set(self.parents)
    self.root_members = {r:[] for r in roots}
    for i, r in enumerate(self.parents):
      self.root_members[r].append(i)
    return self.root_members
  
  def get_node_members(self):
    self.get_root_members()
    return [self.root_members[r] for r in self.parents]
  
N = list(map(int, input().split()))
uf = UnionFind(N[0])
results = [[] for i in range(N[0])]
for i in range(N[1]):
  x, y = list(map(int, input().split()))
  x, y = x - 1, y - 1
  results[x].append(y)
  results[y].append(x)
  uf.union(x, y)
#print(uf.parents)

for i in range(N[2]):
  x, y = list(map(int, input().split()))
  x, y = x - 1, y - 1
  results[x].append(y)
  results[y].append(x)
  
node_members = uf.get_node_members()
#print(node_members, results)

print(" ".join([str(len(set(node_members[i]) - set(results[i])) - 1) for i in range(N[0])]))

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!

class Node:
    def __init__(self, id):
        self.id = id
        self.label = None
        self.friends = []
        self.blocks = []

N,M,K = [int(i) for i in input().split()]

nodes = [Node(i) for i in range(N)]

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

for _ in range(K):
    c,d = [int(i) for i in input().split()]
    nodes[c-1].blocks.append(d-1)
    nodes[d-1].blocks.append(c-1)

def dfs(nodes, i, label):
    if nodes[i].label is None:
        nodes[i].label = label
        for j in nodes[i].friends:
            dfs(nodes, j, label)
        
        #for j in nodes[i].blocks:
        #    dfs(nodes, j, label)
        
label = 0
for i in range(len(nodes)):
    dfs(nodes, i, label)
    label+=1

node_cnts = [0] * (label+1)
for i in range(len(nodes)):
    node_cnts[nodes[i].label] += 1
            
#print(*node_cnts)
result = [0] * len(nodes)
for node in nodes:
    #print(node.id, node.label, node.friends, node.blocks)
    b_cnt = 0
    for b in node.blocks:
        if nodes[b].label == node.label:
            b_cnt += 1
            
    result[node.id] = node_cnts[node.label] - len(node.friends) - b_cnt - 1

print(*result)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        '木の初期化をする'
        self.p = [-1] * n
        self.rank = [1]*n
        self.size = [1]*n
    def find(self, x):
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x, y):
        'rankの低い親を高い方のの親にする'
        if not self.same(x,y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x,y = y,x
            elif self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.size[y] += self.size[x]
            self.p[x] = y
            return True
        else:
            return False

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


n,m,k = map(int,input().split())
uf = UnionFind(n)
ans = [0] * n
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    uf.unite(a,b)
    ans[a] -= 1
    ans[b] -= 1

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

for i in range(n):
    p = uf.find(i)
    ans[i] += uf.size[p] - 1

print(' '.join([str(i) for i in ans]))

Submission status: Runtime Error

Solution code:
n,m,k=map(int,input().split())
q=[]
friend=[0]*n
block=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    q.append({a-1,b-1})
    friend[a-1]+=1
    friend[b-1]+=1
while 1:
    a=q.pop()
    for j in q:
        if len(j&a)!=0:
            j|=a
            count=0
            break
    else:
        q=[a]+q
    if count>len(q):
        break
    count+=1
s=[0]*n
for i in range(n):
  for j in range(len(q)):
    if i in q[j]:
      s[i]=j
for _  in range(k):
    a,b= map(int,input().split())
    block[a-1].append(b-1)
    block[b-1].append(a-1)
ans=[-1]*n
for i in range(n):
  for j in q[s[i]]:
    ans[i]-=block[i].count(j)
for i in range(n):
  ans[i]+=len(q[s[i]])
for i in range(n):
  ans[i]-=friend[i]
print(*ans)

Submission status: Runtime Error

Solution code:
import collections


def friend_candidates(i, friends, visited=None):
    if visited is None:
        visited = set()

    for j in friends[i]:
        if j not in visited:
            yield j
            visited.add(j)
            yield from friend_candidates(j, friends, visited=visited)


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

friends = collections.defaultdict(list)
for _ in range(M):
    A, B = map(int, input().split())
    friends[A].append(B)
    friends[B].append(A)

blockings = collections.defaultdict(list)
for _ in range(K):
    C, D = map(int, input().split())
    blockings[C].append(D)
    blockings[D].append(C)


table = {}
for i in range(1, N + 1):
    if i in table:
        continue

    candidates = list(friend_candidates(i, friends))
    for j in candidates:
        table[j] = candidates


print(
    " ".join(
        str(
            len(table[i])
            - len(friends[i])
            - len(set(blockings[i]).intersection(table[i]))
            - 1
        )
        for i in range(1, N + 1)
    )
)

Submission status: Runtime Error

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

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

Solution code:
from collections import defaultdict

n, m, k = map(int, input().split())
def connection(n):
    connect = defaultdict(set)
    for i in range(n):
        a, b = map(int, input().split())
        connect[a].add(b)
        connect[b].add(a)
    return connect
    
friends = connection(m)
blocks = connection(k)
groups = []
def dfs(start, check_set):
    seen = [False for i in range(n+1)]
    todo = []
    seen[start] = True
    todo.append(start)
    while todo:
        v = todo.pop()
        for w in check_set[v]:
            if not seen[w]:
                seen[w] = True
                todo.append(w)
    return seen

checked_friends = set()
groups = {}
group_num = 0
belong_group = {}
for person in range(n):
    if person in checked_friends:
        continue
    group_num += 1
    seen_friends = dfs(person, friends)
    seen_set = set(i for i, flag in enumerate(seen_friends) if flag)
    seen_len = len(seen_set)
    for i in seen_set:
        belong_group[i] = group_num
    checked_friends |= seen_set
    groups[group_num] = seen_set

print(' '.join(str(len(groups[belong_group[i]])-len(groups[belong_group[i]]&(friends[i]|blocks[i]))-1) for i in range(1, n+1)))

Submission status: Runtime Error

Solution code:
from collections import defaultdict

n, m, k = map(int, input().split())
def connection(n):
    connect = defaultdict(set)
    for i in range(n):
        a, b = map(int, input().split())
        connect[a].add(b)
        connect[b].add(a)
    return connect
    
friends = connection(m)
blocks = connection(k)
groups = []
def dfs(start, check_set):
    seen = [False for i in range(n+1)]
    todo = []
    seen[start] = True
    todo.append(start)
    while todo:
        v = todo.pop()
        for w in check_set[v]:
            if not seen[w]:
                seen[w] = True
                todo.append(w)
    return seen

checked_friends = set()
groups = {}
group_num = 0
belong_group = {}
for person in range(n):
    if person in checked_friends:
        continue
    group_num += 1
    seen_friends = dfs(person, friends)
    seen_set = set(i for i, flag in enumerate(seen_friends) if flag)
    seen_len = len(seen_set)
    for i in seen_set:
        belong_group[i] = group_num
    not_checked_friends |= seen_set
    groups[group_num] = seen_set

print(' '.join(str(len(groups[belong_group[i]])-len(groups[belong_group[i]]&(friends[i]|blocks[i]))-1) for i in range(1, n+1)))

Submission status: Runtime Error

Solution code:
"""
Friend Suggestions
"""

import sys
input = lambda: sys.stdin.readline().rstrip()


class Vertex:
    """A Vertex is a node in a graph."""
    def __init__(self, label=''):
        self.label = label

    def __repr__(self):
        return f'V{self.label}'

    __str__ = __repr__


class Edge(tuple):
    """An Edge is a list of two vertices."""
    def __new__(cls, *vs):
        """The Edge constructor takes two vertices."""
        if len(vs) != 2:
            raise ValueError("Edges must connect exactly two vertices.")
        return tuple.__new__(cls, vs)

    def __repr__(self):
        return f'Edge_{repr(self[0])}_{repr(self[1])}'

    __str__ = __repr__


class Graph(dict):
    """A Graph is a dictionary of dictionaries.
    For vertices a and b, graph[a][b] maps
    to the edge that connects a->b, if it exists."""

    def __init__(self, vs, es):
        """Creates a new graph.
        vs: list of vertices;
        es: list of edges.
        """
        super().__init__()
        for v in vs:
            self.add_vertex(v)
        for e in es:
            self.add_edge(e)

    def add_vertex(self, v):
        """Add a vertex to the graph."""
        self[v] = {}

    def add_edge(self, e):
        """Adds and edge to the graph by adding an entry in both directions."""
        v, w = e
        self[v][w] = e
        self[w][v] = e

    def vertices(self):
        """returns a list of the vertices in graph"""
        vs = []
        for v in self.keys():
            vs.append(v)
        return vs

    def out_vertices(self, v):
        """returns a list of adjacent vertices of the (v)"""
        return self[v].keys()

    def out_edges(self, v):
        """returns a list of edges connected to the (v)"""
        return self[v].values()

    def is_connected(self):
        """returns True if the Graph is conneted and False otherwise"""
        vertices = self.vertices()
        closed = self.BFS(vertices[0])
        return len(vertices) == len(closed)

    def closed_vertices(self, v):
        return self.BFS(v)

    def BFS(self, v):
        """search graph by a BFS: breadth-first-search"""
        worklist = [v]
        closed = []
        while worklist:
            visited = worklist.pop(0)
            closed.append(visited)
            vs = self.out_vertices(visited)
            vs = [v for v in vs if not (v in closed or v in worklist)]
            worklist.extend(vs)
        return closed


def main():
    N, M, K = map(int, input().split())
    ans = [-1] * N

    friend = [list(map(int, input().split())) for _ in range(M)]
    blocks = [list(map(int, input().split())) for _ in range(K)]

    nodes = [Vertex(str(v)) for v in range(N)]
    edges = [Edge(nodes[edge[0]-1], nodes[edge[1]-1]) for edge in friend]
    g = Graph(nodes, edges)

    for i, v in enumerate(nodes):
        closed_graph_list = [str(x) for x in g.closed_vertices(v)]
        closed_graph_list.remove(str(v))
        connected_vertices = [str(x) for x in list(g.out_vertices(v))]
        candidates = list(set(closed_graph_list) - set(connected_vertices))
        ans[i] = candidates

    for block_rel in blocks:
        block_a = block_rel[0] - 1
        block_b = block_rel[1] - 1
        if f'V{block_b}' in ans[block_a]:
            ans[block_a].remove(f'V{block_b}')
        if f'V{block_a}' in ans[block_b]:
            ans[block_b].remove(f'V{block_a}')

    print(*[len(i) for i in ans])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
class Vertex:
    """A Vertex is a node in a graph."""
    def __init__(self, label=''):
        self.label = label

    def __repr__(self):
        return f'V{self.label}'

    __str__ = __repr__


class Edge(tuple):
    """An Edge is a list of two vertices."""
    def __new__(cls, *vs):
        """The Edge constructor takes two vertices."""
        if len(vs) != 2:
            raise ValueError("Edges must connect exactly two vertices.")
        return tuple.__new__(cls, vs)

    def __repr__(self):
        return f'Edge_{repr(self[0])}_{repr(self[1])}'

    __str__ = __repr__


class Graph(dict):
    """A Graph is a dictionary of dictionaries.
    For vertices a and b, graph[a][b] maps
    to the edge that connects a->b, if it exists."""

    def __init__(self, vs, es):
        """Creates a new graph.
        vs: list of vertices;
        es: list of edges.
        """
        super().__init__()
        for v in vs:
            self.add_vertex(v)
        for e in es:
            self.add_edge(e)

    def add_vertex(self, v):
        """Add a vertex to the graph."""
        self[v] = {}

    def add_edge(self, e):
        """Adds and edge to the graph by adding an entry in both directions."""
        v, w = e
        self[v][w] = e
        self[w][v] = e

    def vertices(self):
        """returns a list of the vertices in graph"""
        vs = []
        for v in self.keys():
            vs.append(v)
        return vs

    def out_vertices(self, v):
        """returns a list of adjacent vertices of the (v)"""
        return self[v].keys()

    def out_edges(self, v):
        """returns a list of edges connected to the (v)"""
        return self[v].values()

    def is_connected(self):
        """returns True if the Graph is conneted and False otherwise"""
        vertices = self.vertices()
        closed = self.BFS(vertices[0])
        return len(vertices) == len(closed)

    def closed_vertices(self, v):
        return self.BFS(v)

    def BFS(self, v):
        """search graph by a BFS: breadth-first-search"""
        worklist = [v]
        closed = []
        while worklist:
            visited = worklist.pop(0)
            closed.append(visited)
            vs = self.out_vertices(visited)
            vs = [v for v in vs if not (v in closed or v in worklist)]
            worklist.extend(vs)
        return closed


def main():
    N, M, K = map(int, input().split())
    ans = [-1] * N

    friend = [list(map(int, input().split())) for _ in range(M)]
    blocks = [list(map(int, input().split())) for _ in range(K)]

    nodes = [Vertex(str(v)) for v in range(N)]
    edges = [Edge(nodes[edge[0]-1], nodes[edge[1]-1]) for edge in friend]
    g = Graph(nodes, edges)

    for i, v in enumerate(nodes):
        closed_graph_list = [str(x) for x in g.closed_vertices(v)]
        closed_graph_list.remove(str(v))
        connected_vertices = [str(x) for x in list(g.out_vertices(v))]
        candidates = list(set(closed_graph_list) - set(connected_vertices))
        ans[i] = candidates

    for block_rel in blocks:
        block_a = block_rel[0] - 1
        block_b = block_rel[1] - 1
        if f'V{block_b}' in ans[block_a]:
            ans[block_a].remove(f'V{block_b}')
        if f'V{block_a}' in ans[block_b]:
            ans[block_b].remove(f'V{block_a}')

    print(*[len(i) for i in ans])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
import itertools, math
d,g = list(map(int,input().split()))
pc = [list(map(int,input().split())) for _ in range(d)]
g /= 100

pat = list(itertools.permutations(range(d)))
ans = sum([pc[x][0] for x in range(d)])

def dfs(k, point, cnt, pat):
  global ans
  i = pat[k]
  
  cnt += min(pc[i][0], math.ceil((g-point)/(i+1)))
  point += min(pc[i][0], math.ceil((g-point)/(i+1))) * (i+1)
  point += pc[i][1]//100
  #print(k,i,point,cnt)
  if point >= g:  
    ans  = min(ans, cnt)
    return
  else:
    if k < d-1:
      dfs(k+1, point, cnt, pat)
      

for p in pat:
  dfs(0, 0, 0, list(p))

print(ans)

Submission status: Runtime Error

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(visited)):
    count = 1
    visited = [0*n]
    dfs(root ,  i, graph)
    print(count)
    ans[i] = count - non_candidate[i]
    
print(*ans)

Submission status: Runtime Error

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)
grp_num = max(check)
grp_size = [0]*(grp_num+1)

for i in range(n):
    grp_size[check[i]] += 1
exit()
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: Runtime Error

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

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)

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

Solution code:
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)

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

Solution code:
def DFS(graph,start,mark_dict):
    mark_dict[start] = True
    for target in graph[start]:
      if target not in mark_dict:
        mark_dict[target] = True
        DFS(graph,target,mark_dict)

N,M,K = (int(x) for x in input().split())

friend = {}
for i in range(N):
  friend[i+1] = []
for i in range(M):
  a,b = (int(x) for x in input().split())
  friend[a].append(b)
  friend[b].append(a)

neighbor = [0]*N
for i in range(N):
  dic = {}
  DFS(friend,i+1,dic)
  neighbor[i] = len(dic)

for i in range(K):
  c,d = (int(x) for x in input().split())
  friend[c].append(d)
  friend[d].append(c)
  
for i in range(N):
  neighbor[i] -= len(friend[i+1]) + 1

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

Submission status: Runtime Error

Solution code:
5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5

Submission status: Runtime Error

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

n,m,k = map(int,input().split())
parent_of = [-1 for _ in range(n)]
#print(parent_of)
def root_of(x):
	if parent_of[x] < 0:
		return x
	else:
		parent_of[x] = root_of(parent_of[x])
		return parent_of[x]

def unite(x,y):
	top_root_x = root_of(x)
	top_root_y = root_of(y)
	if top_root_x == top_root_y:
		return False
	if parent_of[top_root_x] > parent_of[top_root_y]:
		top_root_x,top_root_y = top_root_y,top_root_x
	#print(parent_of[top_root_y])
	parent_of[top_root_x] += parent_of[top_root_y]
	parent_of[top_root_y] = top_root_x
	return True

def size_of(x):
		return -parent_of[root_of(x)]

def is_same(x,y):
	return root_of(x) == root_of(y)

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

for _ in range(k):
	c,d = map(int,input().split())
	c -= 1
	d -= 1
	if root_of(c) == root_of(d):
		block_list[c] -= 1
		block_list[d] -= 1
for i in range(n):
	friend_list[i] += size_of(i)
	#print(size_of(i))
print(*friend_list)