Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

a \neq b.

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

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

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

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

Constraints

All values in input are integers.

2 ≤ N ≤ 10^5

0 \leq M \leq 10^5

0 \leq K \leq 10^5

1 \leq A_i, B_i \leq N

A_i \neq B_i

1 \leq C_i, D_i \leq N

C_i \neq D_i

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

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

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

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

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

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

Input

Input is given from Standard Input in the following format:

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

Output

Print the answers in order, with space in between.

Sample Input 1

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

Sample Output 1

0 1 0 1

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

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

Sample Input 2

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

Sample Output 2

0 0 0 0 0

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

Sample Input 3

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

Sample Output 3

1 3 5 4 3 3 3 3 1 0



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


Sample output:
0 1 0 1

Submission status: Wrong Answer

Solution code:
import sys
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)]
f = [0<<(N-1)]*N
def links(x, y):
  f[x-1] = f[x-1] | (1<<(y-1))
  return f

for a,b in ab:
  f = links(a,b)
  f = links(b,a)

print([bin(x) for x in f])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
 
N,M,K = list(map(int,input().split()))
#ab = [list(map(int,input().split())) for _ in range(M)]
#cd = [list(map(int,input().split())) for _ in range(K)]
f = [0<<(N-1)]*N
b = [0<<(N-1)]*N
def links():
  a,b = list(map(int,input().split()))
  a -= 1
  b -= 1
  f[a] = f[a] | (1<<b)
  f[b] = f[b] | (1<<a)
  return f

for _ in range(M):
  f = links()

print(f)

Submission status: Wrong Answer

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

def links(p,f):
  if f == [0<<(N-1)]*N:
    for x, y in ab:
      x -= 1
      y -= 1
      f[x] = f[x] | (1<<y)
      f[y] = f[y] | (1<<x)

  else:
    for i in range(N):
      if f[p] & (i<<N):
        f[p] = f[p] | f[i]
        print(f[p],f[i])
  return f

def blocks(f):
  fb = [0<<(N-1)]*N
  for x, y in cd:
      x -= 1
      y -= 1
      fb[x] = fb[x] | (1<<y)
      fb[y] = fb[y] | (1<<x)
  return [x | y for x, y in zip(f, fb)]

f = [0<<(N-1)]*N
for p in range(N-1):
  f = links(p ,f)

print(f)

Submission status: Wrong Answer

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

def links(p,f):
  if f == [0<<(N-1)]*N:
    for x, y in ab:
      x -= 1
      y -= 1
      f[x] = f[x] | (1<<y)
      f[y] = f[y] | (1<<x)

  else:
    for i in range(N):
      if f[p] & (i<<N):
        f[p] = f[p] | f[i]
        print(f[p],f[i])
  return f

def blocks(f):
  fb = [0<<(N-1)]*N
  for x, y in cd:
      x -= 1
      y -= 1
      fb[x] = fb[x] | (1<<y)
      fb[y] = fb[y] | (1<<x)
  return [x | y for x, y in zip(f, fb)]

f = [0<<(N-1)]*N
for p in range(N-1):
  f = links(p ,f)
fb = blocks(f)
print(f,fb)

Submission status: Wrong Answer

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

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)
print(1)

Submission status: Wrong Answer

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

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)
print(1)

Submission status: Wrong Answer

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

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)
print(1)

Submission status: Wrong Answer

Solution code:
N,M,K = map(int, input().split())
AB = [[int(a) for a in input().split()] for _ in range(M)]
CD = [[int(c) for c in input().split()] for _ in range(K)]
 
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
        
    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
        
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1
                
    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)
    
    def count(self, x):
        return -self.root[self.find_root(x)]
 
 
uf = UnionFind(N)
for t in AB:
    uf.unite(t[0], t[1])

print(1)

Submission status: Wrong Answer

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

N,M,K = list(map(int,input().split()))
ab = [[int(a) for a in input().split()] for _ in range(M)]
cd = [[int(c) for c in input().split()] for _ in range(K)]

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

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

print(1)

Submission status: Wrong Answer

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)



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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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 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 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: Wrong Answer

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

def unite(x, y):
  CX = cluster(x)
  CY = cluster(y)
  if CX != CY:
    if clusterI[x] < clusterI[y]:
      x, y = y, x
    clusterN[x] += clusterN[y]
    clusterI[y] = 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 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: Wrong Answer

Solution code:
n, m, k = map(int, input().split())
clusterN = [1] * n
clusterI = [0] * n
a = b = -1, -1
out = [0] * n
def cluster(x):
  #print("x: {}".format(x))
  if clusterI[x]:
    maxI = cluster(clusterI[x])
    clusterI[x] = maxI
    return maxI
  else:
    return x

def unite(x, y):
  CX = cluster(x)
  CY = cluster(y)
  if CX != CY:
    if clusterI[x] < clusterI[y]:
      x, y = y, x
    print("CX: {}, CY: {}, x: {}, y: {}".format(CX, CY, x, y))
    clusterN[x] += clusterN[y]
    clusterI[y] = x
    

for _ in range(m):

  a, b = map(int, input().split())
  print("cI: {}, cN: {}".format(clusterI, clusterN))

  print("a: {}, b: {}".format(a, b))

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

for _ in range(k):

  a, b = map(int, input().split())
  print("cI: {}, cN: {}".format(clusterI, clusterN))

  print("a: {}, b: {}".format(a, b))
  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: Wrong Answer

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

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

def 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

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

print(1)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m,k = [int(x) for x in input().split()]
l = [[] for i in range(n+1)]
p = []
q = []
d2 = deque()
for i in range(m):
    p.append(list(map(int, input().split())))
for i in range(k):
    q.append(list(map(int, input().split())))
for pi in p:  
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])
#ここまでで、グラフが隣接リスト表記で表される
dist =[[-1] * (n+1) for i in range(n+1)]
for z in range(1,n+1):
  d = deque()
  dist[z][z] = 0
  d.append(z)
  while True:
    v = d.popleft()
    if dist[z][v] >= 2:
      break
    for i in l[v]:
      if dist[z][i] != -1:
        continue
      dist[z][i] = dist[z][v] + 1
      d.append(i)
    if not d:
      break
for qi in q:  
    dist[qi[0]][qi[1]] = -1
    dist[qi[1]][qi[0]] = -1
for i in range(1,n+1):
  print(dist[i].count(2),end=" ")

Submission status: Wrong Answer

Solution code:
N, M, K = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(M)]
CD = [tuple(map(int, input().split())) for i in range(K)]
 
table = [[0]*N for _ in range(N)]
 
for i, row in enumerate(table):
    row[i] = -1
 
for ab in AB:
    a, b = ab
    table[a-1][b-1] = 1
    table[b-1][a-1] = 1
 
for cd in CD:
    c, d = cd
    table[c-1][d-1] = -1
    table[d-1][c-1] = -1

ans = [row.count(0) for row in table]
print(*ans)

Submission status: Wrong Answer

Solution code:
#template
def inputlist(): return [int(j) for j in input().split()]
from collections import Counter
#template
#issueから始める
#Union Find
N,M,K = inputlist()
graph = [[] for _ in range(N)]
#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#初期化
#根なら-size,子なら親の頂点
par = [-1]*(N)
for i in range(M):
    A,B = inputlist()
    graph[A-1].append(B-1)
    graph[B-1].append(A-1)
    unite(A-1,B-1)
bgraph = [[] for _ in range(N)]
for i in range(K):
    C,D = inputlist()
    if same(C-1,D-1):
        bgraph[C-1].append(D-1)
        bgraph[D-1].append(C-1)
li = [0]*N
for i in range(N):
    k = size(i)
    n = len(graph[i])
    m = len(bgraph[i])
    print(k,m,n)
    li[i] = k-n-m-1
print(*li)

Submission status: Wrong Answer

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[x] = CX
    clusterI[y] = 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[i] - 1 for i in range(n)]
print(*out)

Submission status: Wrong Answer

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)


ans = ''

print(ans[:-1])

Submission status: Wrong Answer

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 = []
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: Wrong Answer

Solution code:
N, M, K = map(int, input().split())
friend = [[] for _ in range(N)]
blocked = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
for _ in range(K):
    a, b = map(int, input().split())
    blocked[a-1].append(b-1)
    blocked[b-1].append(a-1)

groups = [None] * N
group_num = -1

for start in range(N):
    if groups[start] is not None:
        continue
    group_num += 1
    stack = []
    stack.append(start)
    groups[start] = group_num 
    while stack:
        person = stack.pop()
        for new_person in friend[person]:
            if groups[new_person] is None:
                stack.append(new_person)
                groups[new_person] = group_num

groups_dict = [[] for _ in range(group_num+1)]
for i, group in enumerate(groups):
    groups_dict[group].append(i)

Submission status: Wrong Answer

Solution code:
N, M, K = map(int, input().split())
friend = [set() for _ in range(N)]
blocked = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    friend[a-1].add(b-1)
    friend[b-1].add(a-1)
for _ in range(K):
    a, b = map(int, input().split())
    blocked[a-1].add(b-1)
    blocked[b-1].add(a-1)

groups = [None] * N
group_num = -1

for start in range(N):
    if groups[start] is not None:
        continue
    group_num += 1
    stack = []
    stack.append(start)
    groups[start] = group_num 
    while stack:
        person = stack.pop()
        for new_person in friend[person]:
            if groups[new_person] is None:
                stack.append(new_person)
                groups[new_person] = group_num

groups_dict = [set() for _ in range(group_num+1)]
for i, group in enumerate(groups):
    groups_dict[group].add(i)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,M,K = list(map(int,input().split()))
f = [[] for i in range(N)]
b = [[] for i in range(N)]
for i in range(M):
  R = list(map(int,input().split()))
  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] + [R[1]-1]
  b[R[1]-1] = b[R[1]-1] + [R[0]-1]

def add_link(ANS):
  for p in range(N):
    t = -1
    while len(ANS[p]) !=t :
      t = len(ANS[p])
      for i in ANS[p]:
          ANS[p] = list(set(ANS[p] + ANS[i]))
    ANS[p] = [x for x in ANS[p] if x not in f[p]+b[p]+[p]]
  return ANS

ANS = f.copy()
ANS = add_link(ANS)

ans = ''
for p in range(N):
  ans += str(len(ANS[p])) + ' '

print(ans[:-1])

Submission status: Wrong Answer

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 = 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 = map(int,input().split())
  i-=1
  j-=1
  block_list[i] |={j}
  block_list[j] |={i}

Submission status: Wrong Answer

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}

Submission status: Wrong Answer

Solution code:
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):
      root = self.root(i)
      merged_size = self.size[i] + self.size[j] 
      self.size[i] = merged_size
      self.size[j] = merged_size
      for node in self.path(i):
        self.l[node] = root
      for node in self.path(j):
        self.l[node] = root
  
  def path(self,i):
    result = [i]
    while self.l[i] != i:
      i = self.l[i]
      result.append(self.l[i])
    return result
  
  def root(self,i):
    while self.l[i] != i:
      i = self.l[i]
    return i
    
  def connected(self,i,j):
    if self.root(i) == self.root(j):
      return True
    else:
      return False
    
  def size(self,i):
    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)]

Submission status: Wrong Answer

Solution code:
import numpy as np
N,M,K = list(map(int,input().split()))
f = [[0]*N for i in range(N)]
b = [[0]*N for i in range(N)]
for i in range(M):
  R = list(map(int,input().split()))
  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] + [R[1]-1]
  b[R[1]-1] = b[R[1]-1] + [R[0]-1]

def add_link(ANS):
  for p in range(N):
    t = -1
    while len(ANS[p]) !=t :
      t = len(ANS[p])
      for i in ANS[p]:
          ANS[p] = list(set(ANS[p] + ANS[i]))
  return ANS

ANS = f.copy()
ANS = add_link(ANS)

ans = ''
for p in range(N):
  ANS[p] = [x for x in ANS[p] if x not in f[p]+b[p]+[p]]
  ans += str(len(ANS[p])) + ' '

print(ans[:-1])

Submission status: Wrong Answer

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

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

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

        if x == y:
            return

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

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

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
"""
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
"""
N,M,K = list(map(int,input().split()))
F = UnionFind(N)
FF = [0]*N
for i in range(M):
    a,b = list(map(int,input().split()))
    F.union(a-1,b-1)
    FF[a-1] += 1
    FF[b-1] += 1
# print(F)
B = UnionFind(N)
for i in range(K):
    a,b = list(map(int,input().split()))
    B.union(a-1,b-1)
# print(B)

Y = []
for i in range(N):
    y = F.size(i) - FF[i]
    for b in B.members(i):
        if b in F.members(i):
            y += -1
    Y.append(str(y))
print(" ".join(Y))

Submission status: Wrong Answer

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
        
N,M,K = list(map(int,input().split()))
F = UnionFind(N)
FF = [0]*N
for i in range(M):
    a,b = list(map(int,input().split()))
    F.union(a-1,b-1)
    FF[a-1] += 1
    FF[b-1] += 1
# print(F)
B = UnionFind(N)
for i in range(K):
    a,b = list(map(int,input().split()))
    B.union(a-1,b-1)
# print(B)

Y = []
for i in range(N):
    y = F.size(i) - FF[i]
    for b in B.members(i):
        if b in F.members(i):
            y += -1
    Y.append(str(y))
print(" ".join(Y))