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:
s = input().split()
n = int(s[0])
m = int(s[1])
kk = int(s[2])
frd=[]
blk=[]
lst_set=[]
ans = ''
for i in range(m):
  swk = input().split() 
  wk = [int(el) for el in swk ]
  frd.append(set(wk))
  ck = False
  for j in range(len(lst_set)):
    if wk[0] in lst_set[j] or wk[1] in lst_set[j] :
      ck = True
      for k in range(len(lst_set)):
        if wk[0] in lst_set[k] or wk[1] in lst_set[k] :
          if j != k :
            lst_set[j] = lst_set[j] | lst_set[k]
            lst_set[k] = set()
        #break
      lst_set[j].add(wk[0])
      lst_set[j].add(wk[1])
      break
  if ck == False:
    lst_set.append(set([wk[0],wk[1]])) 

for i in range(kk):
  swk = input().split() 
  wk = [int(el) for el in swk ]
  blk.append(set(wk))

#print(blk)
#print(frd)
#print(lst_set)
for ii in range(1,n+1):
  wkcnt = 0
  for aa_set in lst_set:
    if ii in aa_set:
      wkset = aa_set
      for fset in frd:
        if ii in fset:
          wkset = wkset - fset
      wkcnt = len(wkset)
      break
  #print(ii,wkset)
  for bset in blk:      
    if ii in bset:
      wkset = wkset - bset
  ans += str(len(wkset)) + ' '
l=len(ans)-1
print(ans[0:l])

Submission status: Runtime Error

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
    par[x] = root(par[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: Runtime Error

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

Solution code:
n, m, k = map(int, input().split())
clusterN = [1] * n
clusterI = list(range(n))
out = [0] * n
def generateC(x):
  if clusterI[x] != x:
    minI = generateC(clusterI[x])
    clusterI[x] = minI
    return minI
  else:
    return x

def unite(x, y):
  CX = generateC(x)
  CY = generateC(y)
  if CX != CY:
    if CX > CY:
      CX, CY = CY, CX
      x, y = y, x
    clusterN[CX] += clusterN[CY]
    clusterI[CY] = CX
    generateC(y)
    

for _ in range(m):
  a, b = map(int, input().split())

  unite(a-1, b-1)
  out[a-1] -= 1
  out[b-1] -= 1

for _ in range(k):

  a, b = map(int, input().split())
  if generateC(a-1) == generateC(b-1):
    out[a1] -= 1
    out[b-1] -= 1
out = [out[i] + clusterN[generateC(i)] - 1 for i in range(n)]
print(*out)

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
clusterN = [1] * n
clusterI = list(range(n))
out = [0] * n
def generateC(x):
  if clusterI[x] != x:
    minI = generateC(clusterI[x])
    clusterI[x] = minI
    return minI
  else:
    return x

def unite(x, y):
  CX = clusterI[x]
  CY = clusterI[y]
  if CX != CY:
    if clusterI[CX] > clusterI[CY]:
      CX, CY = CY, CX
    clusterN[CX] += clusterN[CY]
    clusterI[CY] = CX
    generateC(y)
    generateC(x)
    

for _ in range(m):
  a, b = map(int, input().split())

  unite(a-1, b-1)
  out[a-1] -= 1
  out[b-1] -= 1

for _ in range(k):

  a, b = map(int, input().split())
  if clusterI[a-1] == clusterI[b-1]:
    out[a-1] -= 1
    out[b-1] -= 1
out = [out[i] + clusterN[clusterI[i]] - 1 for i in range(n)]
print(*out)

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
clusterN = [1] * n
clusterI = list(range(n))
out = [0] * n
def generateC(x):
  if clusterI[x] != x:
    minI = generateC(clusterI[x])
    clusterI[x] = minI
    return minI
  else:
    return x

def unite(x, y):
  CX = clusterI[x]
  CY = clusterI[y]
  if CX != CY:
    if clusterI[CX] > clusterI[CY]:
      CX, CY = CY, CX
      x, y = y, x
    clusterN[CX] += clusterN[CY]
    clusterI[CY] = CX
    generateC(y)
    

for _ in range(m):
  a, b = map(int, input().split())

  unite(a-1, b-1)
  out[a-1] -= 1
  out[b-1] -= 1

for _ in range(k):

  a, b = map(int, input().split())
  if clusterI[a-1] == clusterI[b-1]:
    out[a-1] -= 1
    out[b-1] -= 1
out = [out[i] + clusterN[clusterI[i]] - 1 for i in range(n)]
print(*out)

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
clusterN = [1] * n
clusterI = list(range(n))
out = [0] * n

def unite(x, y):
  CX = clusterI[x]
  CY = clusterI[y]
  if CX != CY:
    if CX < CY:
      CX, CY = CY, CX
    clusterN[CX] += clusterN[CY]
    clusterI = [CX if clusterI[i] == CY else clusterI[i] for i in range(n)]
      if clusterI[i] == CY:
        clusterI[i] = CX

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

for _ in range(k):
  a, b = map(int, input().split())
  if clusterI[a-1] == clusterI[b-1]:
    out[a-1] -= 1
    out[b-1] -= 1
out = [out[i] + clusterN[clusterI[i]] - 1 for i in range(n)]
print(*out)

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
clusterN = [1] * n
clusterI = [-1] * n
out = [0] * n
def cluster(x):
  if clusterI[x] >= 0:
    minI = cluster(clusterI[x])
    clusterI[x] = minI
    return minI
  else:
    return x

def unite(x, y):
  CX = cluster(x)
  CY = cluster(y)
  if CX != CY:
    if clusterI[CX] > clusterI[CY]:
      x, y = y, x
    clusterN[CX] += clusterN[CY]
    clusterI[CY] = CX
    

for _ in range(m):

  a, b = map(int, input().split())

  unite(a-1, b-1)
  out[a-1] -= 1
  out[b-1] -= 1

for _ in range(k):

  a, b = map(int, input().split())
  if cluster(a-1) == cluster(b-1):
    out[a-1] -= 1
    out[b-1] -= 1
out = [out[i] + clusterN[cluster(i)] - 1 for i in range(n)]
print(*out)

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
clusterN = [1] * n
clusterI = [-1] * n
out = [0] * n
def cluster(x):
  if clusterI[x] > 0:
    minI = cluster(clusterI[x])
    clusterI[x] = minI
    return minI
  else:
    return x

def unite(x, y):
  CX = cluster(x)
  CY = cluster(y)
  if CX != CY:
    if clusterI[CX] > clusterI[CY]:
      x, y = y, x
    clusterN[CX] += clusterN[CY]
    clusterI[CY] = CX
    

for _ in range(m):

  a, b = map(int, input().split())

  unite(a-1, b-1)
  out[a-1] -= 1
  out[b-1] -= 1

for _ in range(k):

  a, b = map(int, input().split())
  if cluster(a-1) == cluster(b-1):
    out[a-1] -= 1
    out[b-1] -= 1
out = [out[i] + clusterN[cluster(i)] - 1 for i in range(n)]
print(*out)

Submission status: Runtime Error

Solution code:
def main():
    n, m, k = map(int, input().split())
    friends = [[] for _ in range(n+1)]
    block = [[] for _ in range(n+1)]

    for _ in range(m):
        a, b = map(int, input().split())
        friends[a].append(b)
        friends[b].append(a)
    for _ in range(k):
        a, b = map(int, input().split())
        block[a].append(b)
        block[b].append(a)
    # print(friends[1:], block[1:])

    cand_friends = [[] for _ in range(n+1)]
    def search_cand(now_node, i):
        for next_node in friends[now_node]:
            if not(next_node in cand_friends[i]):
                cand_friends[i].append(next_node)
                search_cand(next_node, i)

    for i in range(1, n+1):
        now_node = i
        search_cand(now_node, i)
        if i in cand_friends[i]:
            cand_friends[i].remove(i)
        cand_num = len(cand_friends[i]) - len(friends[i])
        for b in block[i]:
            if b in cand_friends[i]:
                cand_num -= 1
        print(cand_num, end=' ')
    print("")
    # print(cand_friends[1:])

if __name__=='__main__':
    # import time
    # start = time.time()
    main()
    # print(f"{time.time()-start}[s]")

Submission status: Runtime Error

Solution code:
def main():
    n, m, k = map(int, input().split())
    friends = [[] for _ in range(n+1)]
    block = [[] for _ in range(n+1)]

    for _ in range(m):
        a, b = map(int, input().split())
        friends[a].append(b)
        friends[b].append(a)
    for _ in range(k):
        a, b = map(int, input().split())
        block[a].append(b)
        block[b].append(a)
    # print(friends[1:], block[1:])

    cand_friends = [[] for _ in range(n+1)]
    def search_cand(now_node, i):
        for next_node in friends[now_node]:
            if not(next_node in cand_friends[i]):
                cand_friends[i].append(next_node)
                # cand_friends[next_node].append(i)
                search_cand(next_node, i)

    for i in range(1, n+1):
        now_node = i
        search_cand(now_node, i)
        cand_num = len(cand_friends[i]) - len(friends[i]) -1
        for b in block[i]:
            if b in cand_friends[i]:
                cand_num -= 1
        print(cand_num, end=' ')
    print("")
    # print(cand_friends[1:])

if __name__=='__main__':
    # import time
    # start = time.time()
    main()
    # print(f"{time.time()-start}[s]")

Submission status: Runtime Error

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
class uf:
    def __init__(self,n):
        self.n=n
        self.l=[-1]*n
    def ro(self,n):
        if self.l[n]<0:
            return n
        r=self.ro(self.l[n])
        self.l[n]=r
        return r
    def me(self,a,b):
        ra=self.ro(a)
        rb=self.ro(b)
        if ra!=rb:
            self.l[ra]+=self.l[rb]
            self.l[rb]=ra
    def size(self,n):
        return -self.l[self.ro(n)]
    def sa(self,a,b):
        return self.ro(a)==self.ro(b)
N,M,K=map(int,input().split())
u=uf(N)
l=[-1]*N
for i in range(M):
    A,B=map(lambda x: int(x)-1,input().split())
    u.me(A,B)
    l[A]-=1
    l[B]-=1
for i in range(N):
    l[i]+=u.size(i)
for i in range(K):
    C,D=map(lambda x: int(x)-1,input().split())
    if u.sa(C,D):
        l[C]-=1
        l[D]-=1
print(*l)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
S=["0" for i in range(N)]
seen=[]
W="good"
for i in range(M):
    A=input().split()
    if A not in seen:
        seen.append(A)
        if S[int(A[0])-1]=="0":
            S[int(A[0])-1]=A[1]
        else:
            W="bad"
ANS="".join(S)
if (ANS[0]=="0" and len(ANS)!=1) or W=="bad":
    print("-1")
else:
    print(ANS)

Submission status: Runtime Error

Solution code:

N,M,K = list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(M)]
cd = [list(map(int,input().split())) for i in range(K)]
F = [[]*N for i in range(N)]

def union(xx):
  f = [1<<N]*N
  for a,b in xx:
    a -= 1
    b -= 1
    f[a] = f[a] | 1<<(N-b-1)
    f[b] = f[b] | 1<<(N-a-1)
  return f

def F(fi):
  F = [int(i) for i in str(fi) if int(i) > 0]
  return F

f = union(ab)
b = union(cd)

def conv(p):
  res = 1<<N
  for i,x in enumerate(p):
    res = res | x<<(N-i-1)
  return res
  
def add_link(ANS):
  for p,x in enumerate(ANS):
    x = F(x)
    res = 1<<N
    for i in x:
      res = res | ANS[int(i)]
    ANS[p] = res
  return ANS

ANS = f.copy()
pre = []

while ANS != pre:
  pre = ANS.copy()
  ANS = add_link(ANS)

pre = ANS.copy()
fb = [0]*N
ans_p = [0]*N
ans = ''
for p in range(N):
  fb[p] =  f[p] | b[p]
  ANS[p] = ANS[p] | fb[p]
  ANS[p] = ANS[p] ^ fb[p]
  ans_p[p] = sum([int(x) for x in bin(ANS[p])[3:]])
  ans += str(ans_p[p]) + ' '

print(ans[:-1])

Submission status: Runtime Error

Solution code:

N,M,K = list(map(int,input().split()))
F = [[]*N for i in range(N)]
f = [1<<N]*N
b = [1<<N]*N
for i in range(M):
  R = list(map(int,input().split()))
  f[R[0]-1] = f[R[0]-1] | 1<<(N-(R[1]-1)-1)
  f[R[1]-1] = f[R[1]-1] | 1<<(N-(R[0]-1)-1)
  F[R[0]-1] = F[R[0]-1] + [R[1]-1]
  F[R[1]-1] = F[R[1]-1] + [R[0]-1]

for i in range(K):
  R = list(map(int,input().split()))
  b[R[0]-1] = b[R[0]-1] | 1<<(N-(R[1]-1)-1)
  b[R[1]-1] = b[R[1]-1] | 1<<(N-(R[0]-1)-1)

def conv(p):
  res = 1<<N
  for i,x in enumerate(p):
    res = res | x<<(N-i-1)
  return res
  
def add_link(ANS):
  for p,x in enumerate(F):
    res = 1<<N
    for i in x:
      res = res | ANS[int(i)]
    ANS[p] = res
  return ANS

ANS = f.copy()
pre = []
c=0
#while ANS != pre:
while C<1:
  pre = ANS.copy()
  ANS = add_link(ANS)
  c += 1

pre = ANS.copy()
fb = [0]*N
ans_p = [0]*N
ans = ''
for p in range(N):
  fb[p] =  f[p] | b[p]
  ANS[p] = ANS[p] | fb[p]
  ANS[p] = ANS[p] ^ fb[p]
  ans_p[p] = sum([int(x) for x in bin(ANS[p])[3:]])
  ans += str(ans_p[p]) + ' '

print(ans[:-1])

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
friend = [set() for i in range(n)]
block = [set() for i in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    friend[a].add(b)
    friend[b].add(a)
for _ in range(k):
    c, d = map(lambda x: int(x) - 1, input().split())
    block[c].add(d)
    block[d].add(c)


group = [set() for _ in range(n)]
id_ = 0
no_visit = set(range(n))
while len(no_visit) > 0:
    connect = set()
    connect.add(no_visit.pop())
    while len(connect) > 0:
        tmp = connect.pop()
        group[id_].add(tmp)
        new = friend[tmp] & no_visit
        connect = connect | new
        for i in new:
            no_visit.discard(i)
    id_ += 1

ans = [0] * n
for i in range(n):
    ans[i] = len(group[group_id[i]] - friend[i] - block[i]) - 1
print(*ans)

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc157/tasks/abc157_d

class UnionFind:
    def __init__(self, parents):
        self.parents = parents

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

    def unite(self, a, b):
        pa = self.find(a)
        pb = self.find(b)
        if pa == pb:
            return

        self.parents[pa] += self.parents[pb]
        self.parents[pb] = pa

    def same(self, a, b):
        return self.find(a) == self.find(b)

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


N, M, K = map(int, input().split())
union = UnionFind([-1 for i in range(N)])

deg = [0 for _ in range(N)]
to = [[] for _ in range(N)]

for _ in range(M):
    A, B = map(int, input().split())
    deg[A - 1] += 1
    deg[B - 1] += 1
    union.unite(A - 1, B - 1)

for _ in range(K):
    A, B = map(int, input().split())
    to[A - 1].append(B - 1)
    to[B - 1].append(A - 1)

for i in range(N):
    ans = union.size(i) - 1 - deg[i]
    for u in to[i]:
        ans -= union.same(i, u)

    if i == N - 1:
        end = '\n'
    else:
        end = ' '
    print(ans, end=end)

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc157/tasks/abc157_d

class UnionFind:
    def __init__(self, parents):
        self.parents = parents

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

    def unite(self, a, b):
        pa = self.find(a)
        pb = self.find(b)
        if pa == pb:
            return

        self.parents[pa] += self.parents[pb]
        self.parents[pb] = pa

    def same(self, a, b):
        return self.find(a) == self.find(b)

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


N, M, K = map(int, input().split())
union = UnionFind([-1 for i in range(N)])

m = [0 for _ in range(N)]

for _ in range(M):
    A, B = map(int, input().split())
    m[A - 1] += 1
    m[B - 1] += 1
    union.unite(A - 1, B - 1)

for i in range(N):
    m[i] = union.size(i) - 1 - m[i]

for _ in range(K):
    A, B = map(int, input().split())
    m[A - 1] -= union.same(A - 1, B - 1)
    m[B - 1] -= union.same(A - 1, B - 1)

for i, ans in enumerate(m):
    if i == N - 1:
        end = '\n'
    else:
        end = ' '
    print(ans, end=end)

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc157/tasks/abc157_d

class UnionFind:
    def __init__(self, parents):
        self.parents = parents

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

    def unite(self, a, b):
        pa = self.find(a)
        pb = self.find(b)
        if pa == pb:
            return

        self.parents[pa] += self.parents[pb]
        self.parents[pb] = pa

    def same(self, a, b):
        return self.find(a) == self.find(b)

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


N, M, K = map(int, input().split())
union = UnionFind([-1 for i in range(N)])

m = [0 for _ in range(N)]

for _ in range(M):
    A, B = map(int, input().split())
    m[A - 1] += 1
    m[B - 1] += 1
    union.unite(A - 1, B - 1)

for i in range(N):
    m[i] = union.size(i) - 1 - m[i]

for _ in range(K):
    A, B = map(int, input().split())
    m[A - 1] -= union.same(A - 1, B - 1)
    m[B - 1] -= union.same(A - 1, B - 1)

for j, ans in enumerate(m):
    print(ans, end=' ')

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
ans = ["a"]*N
flg = False
for i in range(M):
    s,c = map(int,input().split())
    if ans[s-1] == "a":
        ans[s-1] = str(c)
    elif ans[s-1] != "a" and ans[s-1] != str(c):
        flg = True
if flg:
    print("-1")
else: 
    one_flg = True 
    a = ""  
    if len(ans) == 1:
        print(ans[0])
    else:
        for num in ans:
            if num == "a":
                if one_flg:
                    print("-1")
                    break
                else:
                    a += "0"
            elif num == "0":
                if one_flg:
                    print("-1")
                    break
            else:
                a += num
            one_flg = False   
        else:
            print(a)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

struct UnionFind {
   vector<int> d;
   UnionFind(int n=0): d(n,-1) {}
   int find(int x) {
      if (d[x] < 0) return x;
      return d[x] = find(d[x]);
   }
   bool unite(int x, int y) {
      x = find(x); y = find(y);
      if (x==y) return false;
      if (d[x] > d[y]) swap(x,y);
      d[x] += d[y];
      d[y] = x;
      return true;
   }
   bool same(int x, int y) {return find(x) == find(y);}
   int size(int x) {return -d[find(x)];}
};

int deg[100005];
vector<int> to[100005];

int main() {
   int n, m, k;
   cin >> n >> m >> k;
   UnionFind uf(n);
   rep(i, m) {
      int a, b;
      cin >> a >> b;
      --a; --b;
      deg[a]++;
      deg[b]++;
      uf.unite(a,b);
   }
   rep(i,k) {
      int a, b;
      cin >> a >> b;
      --a; --b;
      to[a].push_back(b);
      to[b].push_back(a);
   }
   rep(i,n) {
      int ans = uf.size(i)-1-deg[i];
      for (int u : to[i]) {
         if (uf.same(i,u)) --ans;
      }
      printf("%d%c", ans, i==n-1?'\n':' ');
   }
   return 0;
}

Submission status: Runtime Error

Solution code:
N,M,K = list(map(int,input().split()))
import sys
input = sys.stdin.readline
from collections import defaultdict
class UF():
  def __init__(self,n):
    self.n_node = n
    self.l = [i for i in range(n)]
    self.size = [1 for i in range(n)]
    self.d = None
  
  def union(self,i,j):
    if not self.connected(i,j):
      iroot,ipath = self.root(i,return_path=True)
      jroot,jpath = self.root(j,return_path=True)
      if len(jpath) < len(ipath):
        for node in ipath + jpath:
          self.l[node] = iroot
      else:
        for node in ipath + jpath:
          self.l[node] = jroot
        
  def root(self,i,return_path=False):
    path = [i]
    while self.l[i] != i:
      i = self.l[i]
      path.append(self.l[i])
    
    if return_path:
      return i,path
    else:
      return i
  
  def connected(self,i,j):
    if self.root(i) == self.root(j):
      return True
    else:
      return False
  
  def simplify(self):
    for node in range(self.n_node):
      root = self.root(self.l[node])
      if self.l[node] != root:
        self.l[node] = root
  
  def calc_connected(self):
    self.d = defaultdict(set)
    self.simplify()
    for idx,root in enumerate(self.l):
      self.d[root] |= {idx}
    
  def connected_set(self,i):
    if self.d is None:
      self.calc_connected()
    return self.d[self.root(i)]
      
uf = UF(N)
direct_connected = defaultdict(set)
for i in range(M):
  i,j = list(map(int,input().split()))
  i-=1
  j-=1
  
  uf.union(i,j)
  direct_connected[i] |= {j}
  direct_connected[j] |= {i}

block_list = defaultdict(set)
for i in range(K):
  i,j = list(map(int,input().split()))
  i-=1
  j-=1
  block_list[i] |={j}
  block_list[j] |={i}

c = Counter(uf.l)
uf.calc_connected()
whole = {i for i in range(N)}
for i in range(N):
  print(len(uf.d[uf.l[i]] - direct_connected[i] - block_list[i]-{i}),end=" ")

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(20000)

def dfs(friends, friend, cluster, visited, belongs, index):
    for i in friends[friend]:
        if not visited[i]:
            visited[i] = True
            cluster.add(i)
            belongs[i] = index
            dfs(friends, i, cluster, visited, belongs, index)

def make_clusters(friends, N):
    clusters = []
    visited = [False] * N
    belongs = [0] * N
    index = 0
    for i in range(N):
        if not visited[i]:
            cluster = set()
            visited[i] = True
            belongs[i] = index
            cluster.add(i)
            dfs(friends, i, cluster, visited, belongs, index)
            index += 1
            clusters.append(cluster)
    return (clusters, belongs)
    
    
N, M, K = map(int, input().split())

friends = [[] for _ in range(N)]
blocks = [set() for _ in range(N)]
clusters = []

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

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

clusters, belongs = make_clusters(friends, N)

clusters_len = len(clusters)
cluster_len = [0] * clusters_len
for i in range(clusters_len):
    cluster_len[i] = len(clusters[i])

for i in range(N):
    ans = cluster_len[belongs[i]] - len(friends[i]) - len(clusters[belongs[i]] & blocks[i]) - 1
    print(ans, end=' ')

print()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

def dfs(friends, friend, cluster, visited, belongs, index):
    for i in friends[friend]:
        if not visited[i]:
            visited[i] = True
            cluster.add(i)
            belongs[i] = index
            dfs(friends, i, cluster, visited, belongs, index)

def make_clusters(friends, N):
    clusters = []
    visited = [False] * N
    belongs = [0] * N
    index = 0
    for i in range(N):
        if not visited[i]:
            cluster = set()
            visited[i] = True
            belongs[i] = index
            cluster.add(i)
            dfs(friends, i, cluster, visited, belongs, index)
            index += 1
            clusters.append(cluster)
    return (clusters, belongs)
    
    
N, M, K = map(int, input().split())

friends = [[] for _ in range(N)]
blocks = [set() for _ in range(N)]
clusters = []

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

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

clusters, belongs = make_clusters(friends, N)

clusters_len = len(clusters)
cluster_len = [0] * clusters_len
for i in range(clusters_len):
    cluster_len[i] = len(clusters[i])

for i in range(N):
    ans = cluster_len[belongs[i]] - len(friends[i]) - len(clusters[belongs[i]] & blocks[i]) - 1
    print(ans, end=' ')

print()

Submission status: Runtime Error

Solution code:
def dfs(friends, friend, cluster, visited, belongs, index):
    for i in friends[friend]:
        if not visited[i]:
            visited[i] = True
            cluster.add(i)
            belongs[i] = index
            dfs(friends, i, cluster, visited, belongs, index)

def make_clusters(friends, N):
    clusters = []
    visited = [False] * N
    belongs = [0] * N
    index = 0
    for i in range(N):
        if not visited[i]:
            cluster = set()
            visited[i] = True
            belongs[i] = index
            cluster.add(i)
            dfs(friends, i, cluster, visited, belongs, index)
            index += 1
            clusters.append(cluster)
    return (clusters, belongs)
    
    
N, M, K = map(int, input().split())

friends = [[] for _ in range(N)]
blocks = [set() for _ in range(N)]
clusters = []

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

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

clusters, belongs = make_clusters(friends, N)

clusters_len = len(clusters)
cluster_len = [0] * clusters_len
for i in range(clusters_len):
    cluster_len[i] = len(clusters[i])

for i in range(N):
    ans = cluster_len[belongs[i]] - len(friends[i]) - len(clusters[belongs[i]] & blocks[i]) - 1
    print(ans, end=' ')

print()

Submission status: Runtime Error

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

# DFSテンプレ、計算量=O(N+M)
# N:頂点の数
# M:辺の数

G = [[] for _ in range(N)]
# graphの入力
for _ in range(M):
    a,b = list(map(int,input().split()))
    G[a-1].append(b-1)
    G[b-1].append(a-1)
# print("G:",G)

KG = [[] for _ in range(N)]
# block graphの入力
for _ in range(K):
    a,b = list(map(int,input().split()))
    KG[a-1].append(b-1)
    KG[b-1].append(a-1)
# print("KG:",KG)

# ここまでエラーなし。

def dfs(G,v):
    # global l
    # nを訪問済みにする
    seen[v] = 1
    # l += 1
    # print(v+1)
    seenV.append(v)
    # vから行ける各頂点next_vについて
    for next_v in G[v]:
        if seen[next_v] == 1:
            continue
        dfs(G,next_v)

# Adj_size = [0]*N
# 全頂点を未訪問に初期化。
Adj = [[] for _ in range(N)]
seen = [0]*N
Y = []
for v in range(N):
    # l = 0
    if seen[v] == 0:
        # 未探索ならdfs発動
        seenV = []
        dfs(G,v)
    
        for sv in seenV:
            Adj[sv] = seenV
    """
        print("dfs done !!!")
    print("v=",v+1,"seen:",seen)
    print("seenV:",seenV)
    print("Adj[",v,"] :",Adj[v])
    """
    
    # 出力
    # y = Adj_size[v] - len(G[v])-1
    y = len(Adj[v]) - len(G[v]) - 1
    for k in KG[v]:
        if k in Adj[v]:
            y += -1
    # print("v=",v+1,"y=",y)
    Y.append(str(y))
    # print("")

# print("ADj",Adj)
# print("Y",Y)
# print("G",G)

print(" ".join(Y))

Submission status: Runtime Error

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

# DFSテンプレ、計算量=O(N+M)
# N:頂点の数
# M:辺の数

G = [[] for _ in range(N)]
# graphの入力
for _ in range(M):
    a,b = list(map(int,input().split()))
    G[a-1].append(b-1)
    G[b-1].append(a-1)
# print("G:",G)

KG = [[] for _ in range(N)]
# block graphの入力
for _ in range(K):
    a,b = list(map(int,input().split()))
    KG[a-1].append(b-1)
    KG[b-1].append(a-1)
# print("KG:",KG)

# ここまでエラーなし。

def dfs(G,v):
    # global l
    # nを訪問済みにする
    seen[v] = 1
    # l += 1
    # print(v+1)
    seenV.append(v)
    # vから行ける各頂点next_vについて
    for next_v in G[v]:
        if seen[next_v] == 1:
            continue
        else:
            dfs(G,next_v)

# Adj_size = [0]*N
# 全頂点を未訪問に初期化。
Adj = [[] for _ in range(N)]
seen = [0]*N
Y = []
for v in range(N):
    # l = 0
    if seen[v] == 0:
        # 未探索ならdfs発動
        seenV = []
        dfs(G,v)
    """
        for sv in seenV:
            Adj[sv] = seenV
    
        print("dfs done !!!")
    print("v=",v+1,"seen:",seen)
    print("seenV:",seenV)
    print("Adj[",v,"] :",Adj[v])
    
    # 出力
    # y = Adj_size[v] - len(G[v])-1
    y = len(Adj[v]) - len(G[v]) - 1
    for k in KG[v]:
        if k in Adj[v]:
            y += -1
    # print("v=",v+1,"y=",y)
    Y.append(str(y))
    print("")

# print("ADj",Adj)
# print("Y",Y)
# print("G",G)

print(" ".join(Y))
"""