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:
import sys
from collections import deque
input = sys.stdin.readline

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

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

    seen = [0]*(N)
    stack = []
    color = {v: -1 for v in range(N)}
    col2v = {color: [] for color in range(N+4)}
    
    def dfs(j, col):
        if seen[j]:
            return
        seen[j] = 1
        stack.append(j)
        color[j] = col
        col2v[col].append(j)
        while stack:
            s = stack[-1]
            if not G[s]:
                stack.pop()
                continue
            g_NO  = G[s].popleft()
            if seen[g_NO]:
                continue
            color[g_NO] = col
            col2v[col].append(g_NO)
            seen[g_NO] = 1
            stack.append(g_NO)
        
    c = 0
    for start in range(N):
        if seen[start]:
            continue
        dfs(start, c)
        c += 1

    ans = []
    for v in range(N):
        kouho = col2v[color[v]]
        # print(kouho)
        block = Block[v]
        # print(block)
        friend = G_original[v]
        # print(friend)
        tmp = set(kouho).difference(block).difference(friend)
        ans.append(len(tmp)-1)
        
        # print("##############")
    print(*ans)
main()

Submission status: Time Limit Exceeded

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

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

    seen = [0]*(N)
    stack = []
    color = {v: -1 for v in range(N)}
    col2v = {color: [] for color in range(N+4)}

    def dfs(j, col):
        if seen[j]:
            return
        seen[j] = 1
        stack.append(j)
        color[j] = col
        col2v[col].append(j)
        while stack:
            s = stack[-1]
            if not G[s]:
                stack.pop()
                continue
            g_NO  = G[s].popleft()
            if seen[g_NO]:
                continue
            color[g_NO] = col
            col2v[col].append(g_NO)
            seen[g_NO] = 1
            stack.append(g_NO)
        
    c = 0
    for start in range(N):
        if seen[start]:
            continue
        dfs(start, c)
        c += 1

    ans = []
    for v in range(N):
        kouho = col2v[color[v]]
        # print(kouho)
        block = Block[v]
        # print(block)
        friend = G_original[v]
        # print(friend)
        tmp = set(kouho).difference(block).difference(friend)
        ans.append(len(tmp)-1)
        
        # print("##############")
    print(*ans)
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

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

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

seen = [0]*(N)
stack = []
color = {v: -1 for v in range(N)}
col2v = {color: [] for color in range(N+4)}

def dfs(j, col):
    if seen[j]:
        return
    seen[j] = 1
    stack.append(j)
    color[j] = col
    col2v[col].append(j)
    while stack:
        s = stack[-1]
        if not G[s]:
            stack.pop()
            continue
        g_NO  = G[s].popleft()
        if seen[g_NO]:
            continue
        color[g_NO] = col
        col2v[col].append(g_NO)
        seen[g_NO] = 1
        stack.append(g_NO)
    
c = 0
for start in range(N):
    if seen[start]:
        continue
    dfs(start, c)
    c += 1

ans = [0]*N
for v in range(N):
    kouho = col2v[color[v]]
    # print(kouho)
    block = Block[v]
    # print(block)
    friend = G_original[v]
    # print(friend)
    tmp = set(kouho).difference(block).difference(friend)
    ans[v] = len(tmp)-1
    # print("##############")
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

class UnionFind():
    def __init__(self, n=0):
        self.d = [-1]*n
    
    def find(self, x):
        if self.d[x] < 0: return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x,y=self.find(x),self.find(y)
        if x==y:return False
        if self.d[x] > self.d[y]: x,y=y,x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(self, x,y): return self.find(x)==self.find(y)
    def size(self,x): return -self.d[self.find(x)]
    
def main():
  N,M,K=map(int,input().split())
  uf=UnionFind(N+1)
  n_friends=defaultdict(int)
  for i in range(M):
    a,b=map(int,input().split())
    uf.unite(a,b)
    n_friends[a] += 1
    n_friends[b] += 1

  B = [set() for _ in range(N+1)]
  for i in range(K):
    c,d=map(int,input().split())
    B[c].add(d)
    B[d].add(c)

  groups=defaultdict(set)
  for i in range(1,N+1):
    g = uf.find(i)
    if g>0:
      groups[g].add(i)

  print(*[len(groups[uf.find(i)].difference(B[i]))-n_friends[i]-1 for i in range(1,N+1)])

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

class UnionFind():
    def __init__(self, n=0):
        self.d = [-1]*n
    
    def find(self, x):
        if self.d[x] < 0: return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x,y=self.find(x),self.find(y)
        if x==y:return False
        if self.d[x] > self.d[y]: x,y=y,x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(self, x,y): return self.find(x)==self.find(y)
    def size(self,x): return -self.d[self.find(x)]
    
N,M,K=map(int,input().split())
uf=UnionFind(N+1)
A = [set() for _ in range(N+1)]
for i in range(M):
  a,b=map(int,input().split())
  uf.unite(a,b)
  A[a].add(b)
  A[b].add(a)
  
B = [set() for _ in range(N+1)]
for i in range(K):
  c,d=map(int,input().split())
  B[c].add(d)
  B[d].add(c)
  
groups=defaultdict(set)
for i in range(1,N+1):
  g = uf.find(i)
  if g>0:
    groups[g].add(i)
    
ans = [len(groups[uf.find(i)].difference(A[i]).difference(B[i]))-1 for i in range(1,N+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 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 same(self, x, y):
        return self.find(x) == self.find(y)

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

relations = [[0 for j in range(N)] for i in range(N)]

tree = UnionFind(N)

for i in range(M):
    a, b = list(map(int, input().split()))
    relations[a-1][b-1] = 1
    relations[b-1][a-1] = 1
    tree.union(a-1, b-1)

for i in range(K):
    c, d = list(map(int, input().split()))
    relations[c-1][d-1] = 2
    relations[d-1][c-1] = 2

cnt = []

for i in range(N):
    cnt.append(0)
    for j in range(N):
        if i == j:
            continue
        if tree.same(i, j) and relations[i][j] == 0:
            cnt[-1] += 1

print(' '.join(list(map(str, cnt))))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m,k = map(int,input().split()) 
g = [set() for _ in range(n)]
bl = [set() for _ in range(n)]

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

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

ans = [0]*n 

def bfs():
    for u in range(n):
        q = deque([u])
        d = [False]*n
        d[u] = True
        l = {u}
        while q:
            v = q.popleft()
            for i in g[v]:
                if d[i] == False:
                    l.add(i)
                    d[i] = True
                    q.append(i)
        for p in l:
            ans[p] = len(l) - len(l&g[p]) - len(l&bl[p]) - 1
    
bfs()

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m,k = map(int,input().split()) 
g = [[] for _ in range(n)]
bl = [[] for _ in range(n)]

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

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


def bfs(u):
    q = deque([u])
    d = [None]*n
    d[u] = 0
    while q:
        v = q.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                q.append(i)
    return d


for i in range(n):
    d = bfs(i)
    ans = len([e for e in d if e != None])-len([e for e in range(len(d)) if d[e] != None and (e in g[i] or e in bl[i])])-1
    print(ans,end = " ")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m,k = map(int,input().split()) 
g = [[] for _ in range(n)]
bl = [[] for _ in range(n)]

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

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


def bfs(u):
    q = deque([u])
    d = [None]*n
    d[u] = 0
    while q:
        v = q.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                q.append(i)
    return d


for i in range(n):
    ans = 0
    d = bfs(i)
    for j in range(len(d)):
        if j != i and d[j] != None and j not in g[i]:
            if j not in bl[i]:
                ans += 1
    print(ans,end = " ")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m,k = map(int,input().split()) 
g = [[] for _ in range(n)]
bl = [[] for _ in range(n)]

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

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


def bfs(u):
    q = deque([u])
    d = [None]*n
    d[u] = 0
    while q:
        v = q.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                q.append(i)
    return d


for i in range(n):
    ans = 0
    d = bfs(i)
    for j in range(len(d)):
        if j != i and d[j] != None and j not in g[i]:
            if j not in bl[i]:
                ans += 1
    print(ans,end = " ")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

wk=deque()
wwk=[]
for i in range(1,n+1):
    wk=deque(ab[i])
    jyo=[i]+ab[i]
    while wk:
        tgwk=wk.pop()
        for j in ab[tgwk]:
            if j not in jyo:
                wwk.append(j)
                jyo.append(j)
                if j not in cd[i]:
                    ka[i]+=1
        if not wk:
            wk=deque(wwk)
            wwk=[]
    print(ka[i],end=' ')

Submission status: Time Limit Exceeded

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    n,m,k = map(int,ipt().split())
    fl = [[] for i in range(n)]
    bl = [set() for i in range(n)]
    for i in range(m):
        a,b = map(int,ipt().split())
        fl[a-1].append(b-1)
        fl[b-1].append(a-1)
    for i in range(k):
        c,d = map(int,ipt().split())
        bl[c-1].add(d-1)
        bl[d-1].add(c-1)

    ans = [-1]*n
    al = [True]*n
    for i in range(n):
        if al[i]:
            q = [i]
            al[i] = False
            st = set([i])
            while q:
                qi = q.pop()
                for j in fl[qi]:
                    if al[j]:
                        st.add(j)
                        al[j] = False
                        q.append(j)
            for j in st:
                ans[j] = len([i for i in st if i not in bl[j]])-len(fl[j])-1

    print(" ".join(map(str,ans)))


    return None

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    n,m,k = map(int,ipt().split())
    fl = [[] for i in range(n)]
    bl = [set() for i in range(n)]
    for i in range(m):
        a,b = map(int,ipt().split())
        fl[a-1].append(b-1)
        fl[b-1].append(a-1)
    for i in range(k):
        c,d = map(int,ipt().split())
        bl[c-1].add(d-1)
        bl[d-1].add(c-1)

    ans = [-1]*n
    al = [True]*n
    for i in range(n):
        if al[i]:
            q = [i]
            al[i] = False
            st = set([i])
            while q:
                qi = q.pop()
                for j in fl[qi]:
                    if al[j]:
                        st.add(j)
                        al[j] = False
                        q.append(j)
            for j in st:
                ans[j] = len(st-bl[j])-len(fl[j])-1

    print(" ".join(map(str,ans)))


    return None

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    n,m,k = map(int,ipt().split())
    fl = [[] for i in range(n)]
    bl = [set() for i in range(n)]
    for i in range(m):
        a,b = map(int,ipt().split())
        fl[a-1].append(b-1)
        fl[b-1].append(a-1)
    for i in range(k):
        c,d = map(int,ipt().split())
        bl[c-1].add(d-1)
        bl[d-1].add(c-1)

    ans = [-1]*n
    for i in range(n):
        if ans[i] != -1:
            continue
        else:
            q = [i]
            al = set([i])
            while q:
                qi = q.pop()
                for j in fl[qi]:
                    if not j in al:
                        al.add(j)
                        q.append(j)
            for j in al:
                ans[j] = len(al-bl[j])-len(fl[j])-1

    print(" ".join(map(str,ans)))


    return None

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

#UnionFindのクラス,0-indexed
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 set([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):
        d = defaultdict(set)
        for i in range(self.n):
            st = set()
            pi = i
            ii = self.parents[pi]
            while ii >= 0:
                st.add(pi)
                pi = ii
                ii = self.parents[pi]
            for j in st:
                self.parents[j] = pi
            d[pi].add(i)
        return d
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    n,m,k = map(int,ipt().split())
    fl = [1]*n
    bl = [set() for i in range(n)]
    fls = []
    uf = UnionFind(n)
    for i in range(m):
        a,b = map(int,ipt().split())
        fl[a-1] += 1
        fl[b-1] += 1
        uf.union(a-1,b-1)
    for i in range(k):
        c,d = map(int,ipt().split())
        bl[c-1].add(d-1)
        bl[d-1].add(c-1)

    ans = [-1]*n
#    print(uf.parents)
    ag = uf.all_group_members()
#    print(ag)
    for i in ag.values():
        for j in i:
#            print(j,i,bl[j],fl[j])
            ans[j] = len(i-bl[j])-fl[j]

    print(" ".join(map(str,ans)))


    return None

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

#UnionFindのクラス,0-indexed
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 set([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):
        d = defaultdict(set)
        for i in range(self.n):
            pi = i
            ii = self.parents[pi]
            while ii >= 0:
                pi = ii
                ii = self.parents[pi]
            if pi != i:
                self.parents[i] = pi
            d[pi].add(i)
        return d
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    n,m,k = map(int,ipt().split())
    fl = [1]*n
    bl = [set() for i in range(n)]
    uf = UnionFind(n)
    for i in range(m):
        a,b = map(int,ipt().split())
        fl[a-1] += 1
        fl[b-1] += 1
        uf.union(a-1,b-1)
    for i in range(k):
        c,d = map(int,ipt().split())
        bl[c-1].add(d-1)
        bl[d-1].add(c-1)

    ans = [-1]*n
#    print(uf.parents)
    ag = uf.all_group_members()
#    print(ag)
    for i in ag.values():
        for j in i:
#            print(j,i,bl[j],fl[j])
            ans[j] = len(i-bl[j])-fl[j]

    print(" ".join(map(str,ans)))


    return None

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

#UnionFindのクラス,0-indexed
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 set([i for i in range(self.n) if self.find(i) == root])
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    n,m,k = map(int,ipt().split())
    fl = [1]*n
    bl = [set() for i in range(n)]
    uf = UnionFind(n)
    for i in range(m):
        a,b = map(int,ipt().split())
        fl[a-1] += 1
        fl[b-1] += 1
        uf.union(a-1,b-1)
    for i in range(k):
        c,d = map(int,ipt().split())
        bl[c-1].add(d-1)
        bl[d-1].add(c-1)

    ans = [-1]*n
    ag = uf.all_group_members()
#    print(ag)
    for i in ag.values():
        for j in i:
#            print(j,i,bl[j],fl[j])
            ans[j] = len(i-bl[j])-fl[j]

    print(" ".join(map(str,ans)))


    return None

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
    
n,m,k=map(int,input().split())
pair=[-1]*n

def main():
#    n,m,k=map(int,input().split())
    g=[[] for i in range(n)]
    x=[[] for i in range(n)]
    a=[0]*m
    b=[0]*m
#    pair=[-1]*n
    for i in range(m):
        ai,bi=map(int,input().split())
        g[ai-1].append(bi-1)
        g[bi-1].append(ai-1)
        a[i]=ai-1
        b[i]=bi-1
        unite(a[i],b[i])
    for i in range(k):
        ci,di=map(int,input().split())
        x[ci-1].append(di-1)
        x[di-1].append(ci-1)

    ii=0        
    ss=size(ii)-len(g[ii])-len(x[ii])-1
    strs=""
    for i in range(n):
        ss=size(i)-1
        rooti=root(i)
        for gi in g[i]:
            if root(gi)==rooti:
                ss-=1
        for xi in x[i]:
            if root(xi)==rooti:
                ss-=1
        strs=strs+" "+str(ss)
    print(strs[1:])
    
def root(x):
    if pair[x]<0:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return False
    if pair[x]>pair[y]:
        x,y=y,x
    pair[x]+=pair[y]    
    pair[y]=x
    return True

def size(x):
    return -pair[root(x)]


main()

Submission status: Time Limit Exceeded

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

def root(x):
    if pair[x]<0:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return False
    if pair[x]>pair[y]:
        x,y=y,x
    pair[x]+=pair[y]    
    pair[y]=x
    return True

def size(x):
    return -pair[root(x)]

icase=0
if icase==0:
    n,m,k=map(int,input().split())
    g=[[] for i in range(n)]
    x=[[] for i in range(n)]
    a=[0]*m
    b=[0]*m
    pair=[-1]*n
    for i in range(m):
        ai,bi=map(int,input().split())
        g[ai-1].append(bi-1)
        g[bi-1].append(ai-1)
        a[i]=ai-1
        b[i]=bi-1
        unite(a[i],b[i])
    for i in range(k):
        ci,di=map(int,input().split())
        x[ci-1].append(di-1)
        x[di-1].append(ci-1)

ii=0        
ss=size(ii)-len(g[ii])-len(x[ii])-1
strs=""
for i in range(n):
    ss=size(i)-1
    rooti=root(i)
    for gi in g[i]:
        if root(gi)==rooti:
            ss-=1
    for xi in x[i]:
        if root(xi)==rooti:
            ss-=1
    strs=strs+" "+str(ss)
print(strs[1:])

Submission status: Time Limit Exceeded

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

def root(x):
    if pair[x]<0:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return False
    if pair[x]>pair[y]:
        x,y=y,x
    pair[x]+=pair[y]    
    pair[y]=x
    return True

def size(x):
    return -pair[root(x)]

icase=0
if icase==0:
    n,m,k=map(int,input().split())
    g=[[] for i in range(n)]
    x=[[] for i in range(n)]
    a=[0]*m
    b=[0]*m
    pair=[-1]*n
    for i in range(m):
        ai,bi=map(int,input().split())
        g[ai-1].append(bi-1)
        g[bi-1].append(ai-1)
        a[i]=ai-1
        b[i]=bi-1
        unite(a[i],b[i])
    for i in range(k):
        ci,di=map(int,input().split())
        x[ci-1].append(di-1)
        x[di-1].append(ci-1)

ii=0        
ss=size(ii)-len(g[ii])-len(x[ii])-1
strs=""
for i in range(n):
    ss=size(i)-1
    rooti=root(i)
    for gi in g[i]:
        if root(gi)==rooti:
            ss-=1
    for xi in x[i]:
        if root(xi)==rooti:
            ss-=1
    strs=strs+" "+str(ss)
print(strs[1:])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
#空のリスト 作った後は普通にappend使えばOK
n,m,k=map(int,input().split())
 
tomodati=[[] for i in range(n+1)]
 
group=[0]*(n+1)
 
block=[0]*(n+1)
 
tansaku=deque()
 
for i in range(m):
    a,b=map(int,input().split())
    tomodati[a].append(b)
    tomodati[b].append(a)
 
num=1
 
for i in range(1,n+1):
    if group[i]==0:
        tansaku.append(i)
        group[i]=num
    else:
        continue
    while len(tansaku)>0:
        for j in tomodati[tansaku[0]]:
            if group[j]==0:
                group[j]=num
                tansaku.append(j)
        tansaku.popleft()
    num+=1
 
for i in range(k):
    c,d=map(int,input().split())
    if group[c]==group[d]:
        block[c]+=1
        block[d]+=1
 
ans=""
 
for i in range(1,n+1):
    ans+=str(group.count(group[i])-len(tomodati[i])-block[i]-1)+" "
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
#空のリスト 作った後は普通にappend使えばOK
n,m,k=map(int,input().split())
 
tomodati=[[] for i in range(n+1)]
 
group=[0]*(n+1)
 
block=[0]*(n+1)
 
tansaku=deque()
 
for i in range(m):
    a,b=map(int,input().split())
    tomodati[a].append(b)
    tomodati[b].append(a)
 
num=1
 
for i in range(1,n+1):
    if group[i]==0:
        tansaku.append(i)
        group[i]=num
    while len(tansaku)>0:
        for j in tomodati[tansaku[0]]:
            if group[j]==0:
                group[j]=num
                tansaku.append(j)
        tansaku.popleft()
    num+=1
 
for i in range(k):
    c,d=map(int,input().split())
    if group[c]==group[d]:
        block[c]+=1
        block[d]+=1
 
ans=""
 
for i in range(1,n+1):
    ans+=str(group.count(group[i])-len(tomodati[i])-block[i]-1)+" "
 
print(ans)