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: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input=sys.stdin.buffer.readline
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
for i in range(n):
  for j in link[i]:
    if s[i][j]==1:
      ans[i]-=1
  for k in block[i]:
    if s[i][k]==1:
      ans[k]-=1
print(*ans)

Submission status: Time Limit Exceeded

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=[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
for i in range(n):
  for j in link[i]:
    if s[i][j]==1:
      ans[i]-=1
  for k in block[i]:
    if s[i][k]==1:
      ans[k]-=1
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
def make_list(length, repeat):
    result = [[] for _ in range(length)]
    for _ in range(repeat):
        a, b = map(lambda x: int(x) - 1, input().split())
        result[a].append(b)
        result[b].append(a)
    return result


def main():
    n, m, k = map(int, input().split())
    friend = make_list(n, m)
    block = make_list(n, k)
    group_id = 1
    group = [0 for _ in range(n)]

    def dfs(start, group_id):
        q = [start]
        if group[start] == 0:
            while q:
                now = q.pop()
                group[now] = group_id
                for nn in friend[now]:
                    if group[nn] == 0:
                        group[nn] = group_id
                        q.append(nn)
            group_id += 1
        return group_id

    for i in range(n):
        group_id = dfs(i, group_id)

    members = [[] for _ in range(group_id)]
    for i in range(n):
        members[group[i]].append(i)

    answer = [0 for _ in range(n)]
    for i in range(n):
        answer[i] = len(members[group[i]]) - len(friend[i]) - len(set(members[group[i]]) & set(block[i])) - 1
    print(" ".join(map(str, answer)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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)
res=[]
for i in range(n):
  l=len((set(link[i]+block[i])&set(s[i])))+1
  res.append(l)
print(*(np.array(ans)-np.array(res)))

Submission status: Time Limit Exceeded

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=[]
    q=deque([i])
    while len(q)>0:
        x=q.pop()
        visited.append(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)
res=[]
for i in range(n):
  l=len((set(link[i]+block[i])&set(s[i])))+1
  res.append(l)
print(*(np.array(ans)-np.array(res)))

Submission status: Time Limit Exceeded

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=[]
    q=deque([i])
    while len(q)>0:
        x=q.pop()
        visited.append(x)
        for j in link[x]:
            if j not in visited:
              if j not in q:
                q.append(j)
    ans.append(len(visited))
    s.append(visited)
res=[]
for i in range(n):
  l=len((set(link[i]+block[i])&set(s[i])))+1
  res.append(l)
print(*(np.array(ans)-np.array(res)))

Submission status: Time Limit Exceeded

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=[]
    q=deque([i])
    while len(q)>0:
        x=q.pop()
        visited.append(x)
        for j in link[x]:
            if j not in visited:
              if j not in q:
                q.append(j)
    ans.append(len(visited))
    s.append(visited)
res=[]
for i in range(n):
  l=1
  for j in s[i]:
    l+=link[i].count(j)
    l+=block[i].count(j)
  res.append(l)
print(*(np.array(ans)-np.array(res)))

Submission status: Time Limit Exceeded

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

not_checked_friends = {i+1 for i in range(n)}
groups = {}
count = 0
belong_group = {}
while not_checked_friends:
    count += 1
    person = list(not_checked_friends).pop()
    seen_friends = dfs(person, friends)
    seen_set = set(i for i, flag in enumerate(seen_friends) if flag)
    for i in seen_set:
        belong_group[i] = count
    not_checked_friends -= seen_set
    groups[count] = 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: Time Limit Exceeded

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 'V{}'.format(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 'Edge_{}_{}'.format(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 'V{}'.format(block_b) in ans[block_a]:
            ans[block_a].remove('V{}'.format(block_b))
        if 'V{}'.format(block_a) in ans[block_b]:
            ans[block_b].remove('V{}'.format(block_a))

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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()))
friend_dict = {i: set() for i in range(1, N + 1)}
block_dict = {i: set() for i in range(1, N + 1)}
for i in range(M):
    node1, node2 = list(map(int, input().split()))
    friend_dict[node1].add(node2)
    friend_dict[node2].add(node1)
for i in range(K):
    node1, node2 = list(map(int, input().split()))
    block_dict[node1].add(node2)
    block_dict[node2].add(node1)

uf = UnionFindLabel(range(1, N + 1))
for node, friends in friend_dict.items():
    for friend_node in friends:
        if not uf.same(node, friend_node):
            uf.union(node, friend_node)

for node in range(1, N + 1):
    cnt = 0
    for mem_node in uf.members(node):
        if mem_node != node and mem_node not in friend_dict[node] and mem_node not in block_dict[node]:
            cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
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 unite(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 same(self, x, y):
        """xとyが同じ集合に属するか否か"""
        return self.find(x) == self.find(y)

    def size(self, x):
        """グループのサイズを返す"""
        return -self.parents[self.find(x)]

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

l = [[False] * N for _ in range(N)]
pena = [0] * N

uf = UnionFind(N)
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    uf.unite(A, B)
    l[A][B] = True
    l[B][A] = True
    pena[A] += 1
    pena[B] += 1

for _ in range(K):
    C, D = map(int, input().split())
    C -= 1
    D -= 1
    if not l[C][D] and uf.same(C, D):
        pena[C] += 1
        pena[D] += 1

ans = [0] * N

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

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

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 unite(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 same(self, x, y):
        """xとyが同じ集合に属するか否か"""
        return self.find(x) == self.find(y)

    def size(self, x):
        """グループのサイズを返す"""
        return -self.parents[self.find(x)]

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

l = [[False] * N for _ in range(N)]
pena = [0] * N

uf = UnionFind(N)
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    uf.unite(A, B)
    l[A][B] = True
    l[B][A] = True
    pena[A] += 1
    pena[B] += 1

for _ in range(K):
    C, D = map(int, input().split())
    C -= 1
    D -= 1
    if not l[C][D] and uf.same(C, D):
        pena[C] += 1
        pena[D] += 1

ans = [0] * N

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

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

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 unite(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 same(self, x, y):
        """xとyが同じ集合に属するか否か"""
        return self.find(x) == self.find(y)

    def size(self, x):
        """グループのサイズを返す"""
        return -self.parents[self.find(x)]

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

l = [[False] * N for _ in range(N)]
pena = [0] * N

uf = UnionFind(N)
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    uf.unite(A, B)
    l[A][B] = True
    l[B][A] = True
    pena[A] += 1
    pena[B] += 1

for _ in range(K):
    C, D = map(int, input().split())
    C -= 1
    D -= 1
    if not l[C][D] and uf.same(C, D):
        pena[C] += 1
        pena[D] += 1

ans = []

for i in range(N):
    ans.append(uf.size(i) - pena[i] - 1)

print(*ans)

Submission status: Time Limit Exceeded

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 unite(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 same(self, x, y):
        """xとyが同じ集合に属するか否か"""
        return self.find(x) == self.find(y)

    def size(self, x):
        """グループのサイズを返す"""
        return -self.parents[self.find(x)]

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

l = [[False] * N for _ in range(N)]
pena = [0] * N

uf = UnionFind(N)
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    uf.unite(A, B)
    l[A][B] = True
    l[B][A] = True
    pena[A] += 1
    pena[B] += 1

for _ in range(K):
    C, D = map(int, input().split())
    C -= 1
    D -= 1
    if not l[C][D] and uf.same(C, D):
        pena[C] += 1
        pena[D] += 1

ans = []

for i in range(N):
    ans.append(uf.size(i) - pena[i] - 1)

print(*ans)

Submission status: Time Limit Exceeded

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)

block_list = [0] * n
friend_list = [0] * 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
answer_array = [-1] * n
for i in range(n):
	answer_array[i] = size_of(i) - friend_list[i] - block_list[i] - 1
	#print(size_of(i))
print(*answer_array)

Submission status: Time Limit Exceeded

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)]

class UnionADD():
  def __init__(self, N):
    self.N = N
    self.f = [1<<self.N]*self.N
    self.b = [1<<self.N]*self.N
    self.fb = [1<<self.N]*self.N
  
  def union(self, xx):
    t = [1<<self.N]*self.N
    for a,b in xx:
      a -= 1
      b -= 1
      t[a] = t[a] | 1<<(self.N-b-1)
      t[b] = t[b] | 1<<(self.N-a-1)
    return t
  
  def conv(self, ab,cd):
    self.f = self.union(ab)
    self.b = self.union(cd)
    self.fb = [x | y for x,y in zip(self.f, self.b)]
  
  def add_link(self, ans):
      for p,x in enumerate(ans):
        for i,y in enumerate(str(bin(x)[3:])):
          if y == '1':
            ans[p] = ans[p] | self.f[i]
      return ans
  
  def link(self,ans):
    pre = []
    ans = self.f.copy()
    while ans != pre:
      pre = ans.copy()
      ans = self.add_link(ans)
    return ans
  
  def count_link(self, ANS):
    ans = []
    for p in range(self.N):
      ANS[p] = ANS[p] | self.fb[p]
      ANS[p] = ANS[p] ^ self.fb[p]
      ans += [bin(ANS[p])[3:].count('1')]
    return ans
    

ua = UnionADD(N)
ua.conv(ab,cd)
ans = [1<<N]*N

ANS = ua.link(ans)
ans = ua.count_link(ANS)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)
N,m,k = [int(x) for x in input().split()]
p = []
q = []
roots = [0]*(N+1)
rootmatome = [0]*(N+1)
tonari = [0]*(N+1)
dame = [0]*(N+1)
for i in range(m):
    p.append(list(map(int, input().split())))
for i in range(k):
    q.append(list(map(int, input().split())))
par = []
for i in range(N+1):
    par.append(i)
def root(x):
    if par[x] == x:
        return x
    return root(par[x])
def unite(x,y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return
    par[rx] = ry
def same(x,y):
    rx = root(x)
    ry = root(y)
    return rx == ry
for i in range(m):
    unite(p[i][0],p[i][1])
for i in range(1,N+1):
  roots[i] = root(i)
for i in range(1,N+1):
    rootmatome[roots[i]] += 1
for i in range(m):
    tonari[p[i][0]] += 1
    tonari[p[i][1]] += 1
for i in range(k):
    if roots[q[i][0]] == roots[q[i][1]]:
        dame[q[i][0]] += 1
        dame[q[i][1]] += 1
for i in range(1,N+1):
    print(rootmatome[roots[i]] - tonari[i] - dame[i] - 1,end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)
N,m,k = [int(x) for x in input().split()]
p = []
q = []
roots = [0]*(N+1)
rootmatome = [0]*(N+1)
tonari = [0]*(N+1)
dame = [0]*(N+1)
for i in range(m):
    p.append(list(map(int, input().split())))
for i in range(k):
    q.append(list(map(int, input().split())))
par = []
for i in range(N+1):
    par.append(i)
#from functools import lru_cache
#@lru_cache(maxsize=1000)
def root(x):
    if par[x] == x:
        return x
    return root(par[x])
def unite(x,y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return
    par[rx] = ry
def same(x,y):
    rx = root(x)
    ry = root(y)
    return rx == ry
for i in range(m):
    unite(p[i][0],p[i][1])
for i in range(1,N+1):
  roots[i] = root(i)
for i in range(1,N+1):
    rootmatome[roots[i]] += 1
for i in range(m):
    tonari[p[i][0]] += 1
    tonari[p[i][1]] += 1
for i in range(k):
    if roots[q[i][0]] == roots[q[i][1]]:
        dame[q[i][0]] += 1
        dame[q[i][1]] += 1
for i in range(1,N+1):
    print(rootmatome[roots[i]] - tonari[i] - dame[i] - 1,end=" ")

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:

    def __init__(self, n):
        self.t = [-1] * (n + 1)

    def flatten(self):
        for i, _ in enumerate(self.t):
            self.find_root(i)

    def union(self, a, b):
        ra = self.find_root(a)
        rb = self.find_root(b)
        if ra != rb:
            self.t[max(ra, rb)] = min(ra, rb)

    def find_root(self, x):
        t = []
        while self.t[x] > 0:
            t.append(x)
            x = self.t[x]
        for _t in t:
            self.t[_t] = x
        return x


def solve(string):
    n, m, k, *abcd = map(int, string.split())
    ab, cd = abcd[:2 * m], abcd[2 * m:]
    fr, br = [0] * (n + 1), [0] * (n + 1)
    uf = UnionFind(n)
    for a, b in zip(*[iter(ab)] * 2):
        fr[a] += 1
        fr[b] += 1
        uf.union(a, b)
    uf.flatten()
    for i, v in enumerate(uf.t):
        if v < 0:
            uf.t[i] = i
    mp = {k: [] for k in set(uf.t[1:])}
    for i, v in enumerate(uf.t[1:], start=1):
        mp[v].append(i)
    for c, d in zip(*[iter(cd)] * 2):
        br[c] += 1 if d in mp[uf.t[c]] else 0
        br[d] += 1 if c in mp[uf.t[d]] else 0
    mp = {k: len(v) for k, v in mp.items()}
    return " ".join([str(mp[uf.t[i]] - 1 - fr[i] - br[i]) for i in range(1, n + 1)])


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:

    def __init__(self, n):
        self.t = [-1] * (n + 1)

    def flatten(self):
        for i, _ in enumerate(self.t):
            self.find_root(i)

    def union(self, a, b):
        ra = self.find_root(a)
        rb = self.find_root(b)
        if ra != rb:
            self.t[max(ra, rb)] = min(ra, rb)

    def find_root(self, x):
        t = []
        while self.t[x] > 0:
            t.append(x)
            x = self.t[x]
        for _t in t:
            self.t[_t] = x
        return x


def solve(string):
    n, m, k, *abcd = map(int, string.split())
    ab, cd = abcd[:2 * m], abcd[2 * m:]
    fr, br = [[] for _ in range(n + 1)], [[] for _ in range(n + 1)]
    uf = UnionFind(n)
    for a, b in zip(*[iter(ab)] * 2):
        fr[a].append(b)
        fr[b].append(a)
        uf.union(a, b)
    uf.flatten()
    for i, v in enumerate(uf.t):
        if v < 0:
            uf.t[i] = i
    mp = {k: i for i, k in enumerate(set(uf.t[1:]))}
    g = [[] for _ in enumerate(mp.keys())]
    for i in range(n + 1):
        if uf.t[i] > 0:
            g[mp[uf.t[i]]].append(i)
    for c, d in zip(*[iter(cd)] * 2):
        br[c].append(d)
        br[d].append(c)

    *fr, = map(set, fr)
    *br, = map(set, br)
    *g, = map(set, g)
    return " ".join([str(len(g[mp[uf.t[i]]] - fr[i] - br[i] - set([i]))) for i in range(1, n + 1)])


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:

    def __init__(self, n):
        self.t = [-1] * (n + 1)

    def flatten(self):
        for i, _ in enumerate(self.t):
            self.find_root(i)

    def union(self, a, b):
        ra = self.find_root(a)
        rb = self.find_root(b)
        if ra != rb:
            self.t[max(ra, rb)] = min(ra, rb)

    def find_root(self, x):
        t = []
        while self.t[x] > 0:
            t.append(x)
            x = self.t[x]
        for _t in t:
            self.t[_t] = x
        return x


def solve(string):
    n, m, k, *abcd = map(int, string.split())
    ab, cd = abcd[:2 * m], abcd[2 * m:]
    fr, br = [[] for _ in range(n + 1)], [[] for _ in range(n + 1)]
    uf = UnionFind(n)
    for a, b in zip(*[iter(ab)] * 2):
        fr[a].append(b)
        fr[b].append(a)
        uf.union(a, b)
    uf.flatten()
    for i, v in enumerate(uf.t):
        if v < 0:
            uf.t[i] = i
    mp = {k: i for i, k in enumerate(set(uf.t[1:]))}
    g = [[] for _ in enumerate(mp.keys())]
    for i in range(n + 1):
        if uf.t[i] > 0:
            g[mp[uf.t[i]]].append(i)
    for c, d in zip(*[iter(cd)] * 2):
        br[c].append(d)
        br[d].append(c)

    *fr, = map(set, fr)
    *br, = map(set, br)
    *g, = map(set, g)
    return " ".join([str(len(g[mp[uf.t[i]]] - set([i]) - fr[i] - br[i])) for i in range(1, n + 1)])


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))