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

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

    def find(self, x):                                          # 根を見つける関数を定義（同時にxを直接根にくっつける操作も行う）
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])        # 右辺で再帰的に根を探索。根に到達すると一つ目のif判定に引っかかるので、
                                                                # 最終的にself.parents[根]が返ってくる。
                                                                # これを左辺に代入することで、根が親になるように変更する。（根までの距離が長いとO(N)になってしまうので）
            return self.parents[x]

    def union(self, x, y):                                      # 二つの木をくっつける（子を多く持つ方を根とした親子関係）。これは破壊的操作を行う。
        x = self.find(x)                                        # xをxの根に置き換える
        y = self.find(y)                                        # yをyの根に置き換える

        if x == y:                                              # 根が同じなら置き換える必要なし
            return

        if self.parents[x] > self.parents[y]:                   # 子がたくさんある方を x とする（出来るだけ浅い木にするため）
            x, y = y, x

        self.parents[x] += self.parents[y]                      # xの子の数を更新
        self.parents[y] = x                                     # yの親を更新

    def same(self, x, y):                                       # xとyが同じ根の子かを判定
        return self.find(x) == self.find(y)

    def size(self, x):                                          # xの根のparent（= 要素数）を返す
        return -self.parents[self.find(x)]

    def members(self, x):                                       # 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):                                          # print(self) での返し方を定義
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


##############################################################################################################

V, E, K = map(int, input().split())                            # V: 頂点数　E: 辺の数

tree = UnionFind(V)

edges = [[] for _ in range(V)]
for _ in range(E):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    tree.union(a, b)
    edges[a].append(b)
    edges[b].append(a)


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



print(tree.parents)

res = []
for x in range(V):
    n = tree.size(x)
    temp = n-1
    for y in edges[x]:
        if tree.same(x,y):
            temp -= 1
    for y in blocks[x]:
        if tree.same(x,y):
            temp -= 1
    res.append(temp)

print(res)

Submission status: Wrong Answer

Solution code:

class UnionFind:
    def __init__(self, n):
        self.par = list(range(n))
        self.rank = [0] * n
        self.size = [1] * n

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

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

        if x == y:
            return

        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        elif self.rank[x] < self.rank[y]:
            x, y = y, x

        self.par[y] = x
        self.size[x] += self.size[y]

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

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


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

friend = [[] for _ in range(N + 1)]
for a, b in X:
    friend[a].append(b)
    friend[b].append(a)

block = [[] for _ in range(N + 1)]
for c, d in Y:
    block[c].append(d)
    block[d].append(c)

t = UnionFind(N + 1)
for a, b in X:
    t.unite(a, b)

ans = []
for i in range(1, N + 1):
    cnt = t.get_size(i) - len(friend[i]) - 1
    for v in block[i]:
        cnt -= int(t.is_same(i, v))
    ans.append(cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque

n,m,k= map(int, input().split())

fri = [[] for _ in range(n+1)]
blo = [[] for _ in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    fri[a].append(b)
    fri[b].append(a)

for i in range(k):
    a, b = map(int, input().split())
    blo[a].append(b)
    blo[b].append(a)


gru = [-1] * (n+1)
gru[0] = 0
gru[1] = 0

nosa = 1
nowgru = 0
grouplist = [[] for _ in range(n+1)]
grouplist[nowgru].append(nosa)
while True:

    d = deque()
    d.append(nosa)

    while d:
        v = d.popleft()
        for i in fri[v]:
            if gru[i] != -1:
                continue
            gru[i] = nowgru
            d.append(i)
            grouplist[nowgru].append(i)

    nowgru +=1
    if -1 in gru:
        nosa = gru.index(-1)
    else:
        break


for i in range(1,n+1):
    g = grouplist[gru[i]]
    ans = len(g)-len(fri[i])-1
    for b in blo[i]:
        if blo in g:
            ans -= 1
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n, m, k = map(int, input().split())
fr = [[] for _ in range(n)]
bl = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    fr[a-1].append(b)
    fr[b-1].append(a)
for _ in range(k):
    c, d = map(int, input().split())
    bl[c-1].append(d)
    bl[d-1].append(c)

ans = [0]*n
nodes_all = []
for i in range(1, n+1):
    if i in nodes_all:
        continue
    q = deque([i])
    tf = [1]*n
    tf[i-1] = 0
    nodes = []
    while q:
        p = q.popleft()
        for node in fr[p-1]:
            if tf[node-1]:
                nodes_all.append(node)
                nodes.append(node)
                tf[node-1] = 0
                q.append(node)
                if node in bl[i-1]:
                    continue
                ans[i-1] += 1
    for node in nodes:
        ans[node-1] = ans[i-1]

ans = [str(ans[i]-len(fr[i])) for i in range(n)]
print(' '.join(ans))

Submission status: Wrong Answer

Solution code:
from collections import deque
n, m, k = map(int, input().split())
fr = [[] for _ in range(n)]
bl = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    fr[a-1].append(b)
    fr[b-1].append(a)
for _ in range(k):
    c, d = map(int, input().split())
    bl[c-1].append(d)
    bl[d-1].append(c)

ans = [0]*n
for i in range(1, n+1):
    q = deque([i])
    tf = [1]*n
    tf[i-1] = 0
    while q:
        p = q.popleft()
        for node in fr[p-1]:
            if tf[node-1]:
                tf[node-1] = 0
                q.append(node)
                # if node in bl[i-1]:
                #     continue
                ans[i-1] += 1

ans = [str(ans[i]-len(fr[i])) for i in range(n)]
print(' '.join(ans))

Submission status: Wrong Answer

Solution code:
N,M,K=map(int,input().split())
friend=[[] for _ in range (N)]
block=[[] for _ in range(N)]

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

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


ans=[]
for i in range(N):
    count=0
    if len(friend[i])==0:
        break
    for num in friend[i]:
        if len(friend[num])==0:
            break
        for num1 in friend[num]:
            if num1 not in friend[i] and num1 not in block[i] and num1!=i:
                count+=1
    ans.append(count)

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

Submission status: Wrong Answer

Solution code:
print("A")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n,m,k=list(map(int,input().split()))
d=defaultdict(list)
for i in range(m+k):
    a,b=list(map(int,input().split()))
    d[a-1].append(b-1)
    d[b-1].append(a-1)
c=[n-1]*n
for i in range(n):
    c[i]-=len(d[i])
print(*c)

Submission status: Wrong Answer

Solution code:
n,m,k = map(int,input().split())
ab = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
cd = [[] for i in range(n)]
for i in range(k):
    c,d = map(int,input().split())
    cd[c-1].append(d-1)
    cd[d-1].append(c-1)
    
ans = [0 for i in range(n)]
data = [0 for i in range(n)] #見たら1
for i in range(n): #自分がi
    if(data[i] != 0):
        break
    data[i] = 1
    data2 = ab[i] + [i]
    for j in ab[i]:
        data[j] = 1
    new_friends = [ab[i]]
    for fris in new_friends:
        new = []
        for fri in fris: #この層の友人を１人選ぶ
            for frfr in ab[fri]: #その友人の友人
                if(data[frfr] == 0):
                    data[frfr] = 1
                    new.append(frfr)
                    data2.append(frfr)
        if(len(new)==0):
            break
        else:
            new_friends.append(new)

    sam = len(data2)
    for j in data2:
        count = sam
        for ng in cd[j]:
            if(ng in data2):
                count -= 1
        ans[j] = count - len(ab[j]) -1 


print(*ans)

Submission status: Wrong Answer

Solution code:
import copy
n, m, k = map(int, input().split())

friends = [[] for i in range(n)]
blocks = [[] for i in range(n)]
not_candidates = [[i] for i in range(n)]
candidates = [0 for i in range(n)]

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

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

# print(friends)
# print(not_candidates)

for i in range(n):
    j = copy.copy(friends[i])
    while len(j) > 0:
        k = j.pop()
        for l in friends[k]:
            if l not in not_candidates[i]:
                if l not in blocks[i]:    
                    candidates[i] += 1
                j.append(l)
                not_candidates[i].append(l)
                
print(candidates)

Submission status: Wrong Answer

Solution code:
class UnionFind:
  def __init__(self, n):
    self.p = [-1]*n
    # union by rank
    self.r = [1]*n
 
  def find(self, x):
    if self.p[x] < 0:
      return x
    else:
      self.p[x] = self.find(self.p[x])
      return self.p[x]

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

    if rx != ry:
      if self.r[rx] > self.r[ry]:
        rx, ry = ry, rx
      if self.r[rx] == self.r[ry]:
        self.r[ry] += 1
      self.p[ry] += self.p[rx]
      self.p[rx] = ry

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

  def count_member(self, x):
    return -self.p[self.find(x)]
  
n,m,k=map(int,input().split())
uf=UnionFind(n)
ab,cd=[],[]
for i in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  uf.union(a,b)
  ab.append((a,b))
for i in range(k):
  c,d=map(int,input().split())
  c-=1
  d-=1
  if not uf.same(c,d):
    uf.union(c,d)
  cd.append((c,d))
cnt=[]
for i in range(n):
  t=uf.count_member(i)-1
  cnt.append(t)
for a,b in ab:
  if uf.same(a,b):
    cnt[a]-=1
    cnt[b]-=1
for c,d in cd:
  if uf.same(c,d):
    cnt[c]-=1
    cnt[d]-=1
print(*cnt)

Submission status: Wrong Answer

Solution code:
def find(i):
    x = i
    while x!=G[x][0]:
        x = G[x][0]
    return x
def union(i,j):
    ai = find(i)
    ni = G[ai][1]
    aj = find(j)
    nj = G[aj][1]
    if ai!=aj:
        if ni>=nj:
            G[aj][0] = ai
            if G[aj][1]==G[ai][1]:
                G[ai][1] += 1
            G[ai][2] += G[aj][2]
        else:
            G[ai][0] = aj
            G[aj][2] += G[ai][2]
N,M,K = map(int,input().split())
G = {i:[i,0,1] for i in range(1,N+1)}
A = {i:[] for i in range(1,N+1)}
B = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int,input().split())
    union(a,b)
    A[a].append(b)
    A[b].append(a)
for _ in range(K):
    c,d = map(int,input().split())
    B[c].append(d)
    B[d].append(c)
C = []
for i in range(1,N+1):
    ai = find(i)
    n = G[ai][2]
    m = 0
    for j in A[i]:
        if ai==find(j):
            m += 1
    k = 0
    for j in B[i]:
        if ai==find(j):
            k += 1
    n = n-m-k
    C.append((n*(n-1))//2)
print(*C)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n
 
    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self._root(self.table[x])
            return self.table[x]
 
    def count(self, x):
        return -self.table[self._root(x)]
 
    def find(self, x, y):
        return self._root(x) == self._root(y)
 
    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1

N, M, K = map(int, input().split())
ins_friend = UnionFind(N)
friends = [0 for i in range(N)]
blocks = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    ins_friend.union(a-1, b-1)
    friends[a-1] += 1
    friends[b-1] += 1
for _ in range(K):
    c, d = map(int, input().split())
    blocks[c-1].add(d-1)
    blocks[d-1].add(c-1)
ans = [0 for i in range(N)]
for i in range(N):
    ans[i] = ins_friend.count(i) - 1 - friends[i]
    for x in range(len(blocks[i])):
        if ins_friend.find(i, x) == True:
            ans[i] -= 1
print(*ans)

Submission status: Wrong Answer

Solution code:
N,M,K = map(int,input().split())
friend = [[] for i in range(N)]
block = [[] for i in range(N)]


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

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

from collections import deque

li = []

def bfs(a):
    que = deque(friend[a-1])
    memo = [-1]*N
    memo[a-1]= 1
    counter = 0
    while que:
        human = que.popleft()
       
        if memo[human-1]==-1 and not(human in friend[a-1]) and not(human in block[a-1]):
            counter += 1

            for i in friend[human-1]:
                if memo[i-1]== -1:
                    que.append(i)
                 
                    
        if human in friend[a-1] and memo[human-1]==-1:
            for i in friend[human-1]:
                if memo[i-1]== -1:
                    que.append(i)
         
        
   
        memo[human-1]=1

    li.append(counter)

for i in range(1,N+1):
   bfs(i)

print(" ".join(list(map(str,li))))

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x, y = y, x
            par[x] += par[y]
            par[y] = x
            return True
    def same(x, y):
        return find(x) == find(y)

    def find2(x):
        if par2[x] < 0:
            return x
        else:
            par2[x] = find2(par2[x])
            return par2[x]

    def unite2(x, y):
        x = find2(x)
        y = find2(y)
        if x == y:
            return False
        else:
            if par2[x] > par2[y]:
                x, y = y, x
            par2[x] += par2[y]
            par2[y] = x
            return True

    def same2(x, y):
        return find2(x) == find2(y)

    n, m, k = map(int, input().split())
    par = [-1] * n
    par2 = [-1] * n
    friend = {e:[] for e in range(n)}
    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        unite(a, b)
        friend[a].append(b)
        friend[b].append(a)
    for _ in range(k):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        unite2(c, d)
    for i1 in range(n):
        r = 0
        for i2 in range(n):
            if i1 == i2 or i2 in friend[i1] or not same(i1, i2) or same2(i1, i2):
                continue
            else:
                r += 1
        print(r, end=' ')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

n, m, k = map(int, input().split())
f = {i: set() for i in range(1, n+1)}
BL = {i: set() for i in range(1, n+1)}
ans = [0] * n
for _ in range(m):
    a, b = map(int, input().split())
    f[a].add(b)
    f[b].add(a)
for _ in range(k):
    c, d = map(int, input().split())
    BL[c].add(d)
    BL[d].add(c)
for i in range(1, n+1):
    ff = f[i].copy()
    q = deque(f[i])
    while q:
        t = q.popleft()
        for x in f[t]:
            if x not in ff:
                ff.add(x)
                q.append(x)
    ans[i-1] = len(ff - f[i] - BL[i]) - 1
print(*ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)

def dfs(x):
    if seen[x-1]==0:
        uni[cnt].add(x)
        seen[x-1]=1
        for i in fri[x-1]:
            dfs(i)
    

n,m,k=map(int,input().split())

fri=[[] for i in range(n)]
blk=[set() for i in range(n)]

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

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


seen=[0 for i in range(n)]

uni=[]
cnt=0
for i in range(1,n+1):
    if seen[i-1]==0:
        uni.append(set())
        dfs(i)
        cnt+=1

seq=[0 for i in range(n)]

print(*seq)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)

def dfs(x):
    if seen[x-1]==0:
        uni[cnt].append(x)
        seen[x-1]=1
        for i in fri[x-1]:
            dfs(i)
    

n,m,k=map(int,input().split())

fri=[[] for i in range(n)]
blk=[[] for i in range(n)]

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

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


seen=[0 for i in range(n)]

uni=[]
cnt=0
for i in range(1,n+1):
    if seen[i-1]==0:
        uni.append([])
        dfs(i)
        cnt+=1

seq=[0 for i in range(n)]

print(*seq)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)

def dfs(x):
    if seen[x-1]==0:
        uni[cnt].add(x)
        seen[x-1]=1
        for i in fri[x-1]:
            dfs(i)
    

n,m,k=map(int,input().split())

fri=[[] for i in range(n)]
blk=[set() for i in range(n)]

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

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


seen=[0 for i in range(n)]

uni=[]
cnt=0
for i in range(1,n+1):
    if seen[i-1]==0:
        uni.append(set())
        dfs(i)
        cnt+=1

seq=[0 for i in range(n)]


print(*seq)

Submission status: Wrong Answer

Solution code:
n,m,k=[int(x) for x in input().rstrip().split()]
l=[[] for i in range(n)]
for i in range(m):
  a,b=[int(x) for x in input().rstrip().split()]
  l[a-1].append(b-1)
  l[b-1].append(a-1)

done=[0 for i in range(n)]

ans=[0 for i in range(n)]
def bfs(i):
  moment=[]
  cnt=0
  que=[i]
  if done[i]==0:
    while(que):
      now=que.pop(0)
      moment.append(now)
      done[now]=i+1
      cnt+=1
      for j in l[now]:
        if done[j]==0:
          done[j]=i+1
          que.append(j)
    for s in moment:
      if done[s]==i+1:
        ans[s]=cnt

for i in range(n):
  bfs(i)
  
for i in range(k):
  c,d=[int(x) for x in input().rstrip().split()]
  if ans[c-1]==ans[d-1]:
    if ans[c-1]!=1 and ans[d-1]!=1:
      ans[c-1]-=1
      ans[d-1]-=1

for i in range(n):
  ans[i]=ans[i]-(len(l[i])+1)
print(*ans)

Submission status: Wrong Answer

Solution code:
n,m,k=[int(x) for x in input().rstrip().split()]
l=[[] for i in range(n)]
for i in range(m):
  a,b=[int(x) for x in input().rstrip().split()]
  l[a-1].append(b-1)
  l[b-1].append(a-1)

done=[0 for i in range(n)]
ans=[0 for i in range(n)]

def bfs(i):
  cnt=0
  moment=str(i)
  que=[i]
  done[i]=1
  while(que):
    now=que.pop(0)
    cnt+=1
    for j in l[now]:
      if done[j]!=1:
        done[j]=1
        moment+=str(j)
        que.append(j)

  for j in moment:
    if ans[int(j)]==0:
      ans[int(j)]=cnt

for i in range(n):
  if ans[i]==0:
    bfs(i)

for i in range(n):
  ans[i] -= (len(l[i])+1)

for i in range(k):
  c,d=[int(x) for x in input().rstrip().split()]
  if ans[c-1]==ans[d-1]:
    if ans[c-1]!=0:
      ans[c-1]-=1
      
    if ans[d-1]!=0:    
      ans[d-1]-=1

print(*ans)

Submission status: Wrong Answer

Solution code:
n,m,k=[int(x) for x in input().rstrip().split()]
l=[[] for i in range(n)]
for i in range(m):
  a,b=[int(x) for x in input().rstrip().split()]
  l[a-1].append(b-1)
  l[b-1].append(a-1)

block=[[] for i in range(n)]
done=[0 for i in range(n)]
ans=[-1 for i in range(n)]

def bfs(i):
  cnt=0
  moment=str(i)
  que=[i]
  done[i]=1
  while(que):
    now=que.pop(0)
    cnt+=1
    for j in l[now]:
      if done[j]!=1:
        done[j]=1
        moment+=str(j)
        que.append(j)

  for j in moment:
    if ans[int(j)]==-1:
      ans[int(j)]=cnt
  
for i in range(n):
  if ans[i]==-1:
    bfs(i)

for i in range(k):
  c,d=[int(x) for x in input().rstrip().split()]
  if ans[c-1]==ans[d-1]:
    block[c-1].append(d-1)
    block[d-1].append(c-1)

for i in range(n):
  ans[i] -= (len(l[i])+len(block[i])+1)
print(*ans)

Submission status: Wrong Answer

Solution code:
n,m,k=[int(x) for x in input().rstrip().split()]
l=[[] for i in range(n)]
for i in range(m):
  a,b=[int(x) for x in input().rstrip().split()]
  l[a-1].append(b-1)
  l[b-1].append(a-1)

block=[[] for i in range(n)]
done=[0 for i in range(n)]
ans=[-1 for i in range(n)]

def bfs(i):
  cnt=0
  moment=str(i)
  que=[i]
  while(que):
    now=que.pop(0)
    for j in l[now]:
      if done[j]==1:
        continue
      else:
        cnt+=1
        done[j]=1
        moment+=str(j)
        que.append(j)
  for j in moment:
    if ans[int(j)]==-1:
      ans[int(j)]=cnt
  
for i in range(n):
  bfs(i)

for i in range(k):
  c,d=[int(x) for x in input().rstrip().split()]
  if ans[c-1]==ans[d-1]:
    block[c-1].append(d-1)
    block[d-1].append(c-1)

for i in range(n):
  ans[i] -= (len(l[i])+len(block[i])+1)
print(*ans)

Submission status: Wrong Answer

Solution code:
n,m,k=[int(x) for x in input().rstrip().split()]
l=[[] for i in range(n)]
for i in range(m):
  a,b=[int(x) for x in input().rstrip().split()]
  l[a-1].append(b-1)
  l[b-1].append(a-1)

block=[[] for i in range(n)]
done=[0 for i in range(n)]
ans=[-1 for i in range(n)]

def bfs(i):
  cnt=1
  moment=str(i)
  que=[i]
  while(que):
    now=que.pop(0)
    done[now]=1
    for j in l[now]:
      if done[j]==1:
        continue
      else:
        cnt+=1
        done[j]=1
        moment+=str(j)
        que.append(j)
  for j in moment:
    if ans[int(j)]==-1:
      ans[int(j)]=cnt
  
for i in range(n):
  bfs(i)

for i in range(k):
  c,d=[int(x) for x in input().rstrip().split()]
  if ans[c-1]==ans[d-1]:
    block[c-1].append(d-1)
    block[d-1].append(c-1)

for i in range(n):
  ans[i] -= (len(l[i])+len(block[i])+1)
print(*ans)

Submission status: Wrong Answer

Solution code:
n,m,k=map(int,input().split())
Friends=[[] for i in range(n)]
Blocks=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    Friends[a].append(b)
    Friends[b].append(a)
for i in range(k):
    a,b=map(int,input().split())
    a-=1
    b-=1
    Blocks[a].append(b)
    Blocks[b].append(a)
from collections import deque
for i in range(n):
    L=set()
    queue=deque(Friends[i])
    while queue:
        now=queue.popleft()
        for k in Friends[now]:
            if not(k in L):
                L.add(k)
                queue.append(k)
    print(len(L-set(Friends[i])-set(Blocks[i]))-1,end=' ')

Submission status: Wrong Answer

Solution code:
n,m,k = map(int,input().split())
friends = [list(map(int,input().split())) 
           for nesya in range(m)]
blocks = [list(map(int,input().split()))
          for motsu in range(k)]
normal= [[i+1 for i in range(n)] for voca in range(n)]
for f in friends:
  a = f[0]
  b = f[1]
  normal[a-1].remove(b)
  normal[b-1].remove(a)
for bl in blocks:
  c = bl[0]
  d = bl[1]
  normal[c-1].remove(d)
  normal[d-1].remove(c)
ans = []
for nor in normal:
  ans.append(str(len(nor)-1))
print(' '.join(ans))

Submission status: Wrong Answer

Solution code:
from collections import deque

n,m,k = map(int,input().split())
a = []
c = []
for i in range(m):
    a.append(list(map(int,input().split())))
for i in range(k):
    c.append(list(map(int,input().split())))
# print(a)
cango = [[]for i in range(n)]
for i in a:
    cango[i[0]-1].append(i[1]-1)
    cango[i[1]-1].append(i[0]-1)
# print(cango)

cannotgo=[[]for i in range(n)]
for i in c:
    cannotgo[i[0]-1].append(i[1]-1)
    cannotgo[i[1]-1].append(i[0]-1)
# print(cannotgo)
alre = [False]*n
parent = [-1]*n
gro = {}

# print(gro)
for i in range(n):
    if alre[i]==True:
        continue
    gro[i]=set([i])
    stack = [i]
    while stack:
        x = stack.pop()
        alre[x]=True
        parent[x]=i
        for to in cango[x]:
            if alre[to]:
                continue
            print(to)
            gro[i].add(to)
            stack.append(to)
# print(gro)
# print(parent)
ans = [0]*n
# print(ans)
for iam in range(n):
    group = gro[parent[iam]]
    tmp_ans = len(group)-len(cango[iam])-1
    for block in cannotgo[iam]:
        if block in group:
            tmp_ans -=1
    ans[iam]=tmp_ans
print(*ans, sep=' ')

Submission status: Wrong Answer

Solution code:
from collections import deque

n,m,k = map(int,input().split())
a = []
c = []
for i in range(m):
    a.append(list(map(int,input().split())))
for i in range(k):
    c.append(list(map(int,input().split())))
# print(a)
cango = [[]for i in range(n)]
for i in a:
    cango[i[0]-1].append(i[1]-1)
    cango[i[1]-1].append(i[0]-1)
# print(cango)

cannotgo=[[]for i in range(n)]
for i in c:
    cannotgo[i[0]-1].append(i[1]-1)
    cannotgo[i[1]-1].append(i[0]-1)
print(cannotgo)
alre = [False]*n
parent = [-1]*n
gro = {}

# print(gro)
for i in range(n):
    if alre[i]==True:
        continue
    gro[i]=set([i])
    stack = [i]
    while stack:
        x = stack.pop()
        alre[x]=True
        parent[x]=i
        for to in cango[x]:
            if alre[to]:
                continue
            print(to)
            gro[i].add(to)
            stack.append(to)
# print(gro)
# print(parent)
ans = [0]*n
# print(ans)
for iam in range(n):
    group = gro[parent[iam]]
    tmp_ans = len(group)-len(cango[iam])-1
    for block in cannotgo[iam]:
        if block in group:
            tmp_ans -=1
    ans[iam]=tmp_ans
print(*ans, sep=' ')

Submission status: Wrong Answer

Solution code:
from collections import deque

n,m,k = map(int,input().split())
a = []
c = []
for i in range(m):
    a.append(list(map(int,input().split())))
for i in range(k):
    c.append(list(map(int,input().split())))
# print(a)
cango = [[]for i in range(n)]
for i in a:
    cango[i[0]-1].append(i[1]-1)
    cango[i[1]-1].append(i[0]-1)
print(cango)

cannotgo=[[]for i in range(n)]
for i in c:
    cannotgo[i[0]-1].append(i[1]-1)
    cannotgo[i[1]-1].append(i[0]-1)
print(cannotgo)
alre = [False]*n
parent = [-1]*n
gro = {}

# print(gro)
for i in range(n):
    if alre[i]==True:
        continue
    gro[i]=set([i])
    stack = [i]
    while stack:
        x = stack.pop()
        alre[x]=True
        parent[x]=i
        for to in cango[x]:
            if alre[to]:
                continue
            print(to)
            gro[i].add(to)
            stack.append(to)
# print(gro)
# print(parent)
ans = [0]*n
# print(ans)
for iam in range(n):
    group = gro[parent[iam]]
    tmp_ans = len(group)-len(cango[iam])-1
    for block in cannotgo[iam]:
        if block in group:
            tmp_ans -=1
    ans[iam]=tmp_ans
print(*ans, sep=' ')

Submission status: Wrong Answer

Solution code:
n, m, k = map(int, input().split())
friend = [list(map(int, input().split())) for i in range(m)]
block = [list(map(int, input().split())) for i in range(k)]

res = [0 for i in range(n)]

Submission status: Wrong Answer

Solution code:
n, m, k = map(int, input().split())
friend = []
for i in range(m):
    friend.append(list(map(int, input().split())))
block = []
for i in range(k):
    block.append(list(map(int, input().split())))

res = [0 for i in range(n)]

Submission status: Wrong Answer

Solution code:
n, m, k = map(int, input().split())
friend = []
for i in range(m):
    friend.append(list(map(int, input().split())))
block = []
for i in range(k):
    block.append(list(map(int, input().split())))

res = [0 for i in range(n)]
mat = [[0 for i in range(n)] for i in range(n)]