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:
N, M, K = [int(i) for i in input().split()]
F = [[int(i) for i in input().split()] for _ in range(M)]
B = [[int(i) for i in input().split()] for _ in range(K)]
clusters = []
cluster_label = [-1 for _ in range(N+1)]
friends = [[] for _ in range(N+1)]
blocks = [[] for _ in range(N+1)]
def make_cluster(i,j):
  cluster_label[i] = len(clusters)
  cluster_label[j] = len(clusters)
  clusters.append([i,j])
def search_cluster(i):
  return cluster_label[i]
def add_cluster(i, n):
  cluster_label[i] = n
  clusters[n].append(i)
def join_clusters(n, m):
  tmp = min(n, m)
  m = max(n, m)
  n = tmp
  for mem in clusters[m]:
    cluster_label[mem] = n
  clusters[n].extend(clusters[m])
  clusters[m] = -1
for i,j in F:
  p, q = search_cluster(i), search_cluster(j)
  friends[i].append(j)
  friends[j].append(i)
  if(p+q==-2):
    make_cluster(i, j)
  elif(p-q==0):
    continue
  elif(p==-1):
    add_cluster(i, q)
  elif(q==-1):
    add_cluster(j, p)
  else:
    join_clusters(p, q)
for i,j in B:
  blocks[i].append(j)
  blocks[j].append(i)
clusters.append([-1])
[print(len([j for j in clusters[cluster_label[i]] if((j not in friends[i])&(j not in blocks[i])&(j!=i))])) for i in range(1,N+1)]

Submission status: Wrong Answer

Solution code:
from collections import deque

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

F=[[] for _ in range(N)]
B=[[] for _ in range(N)]


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

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

q=deque([])
G=[]
visited=[0]*N
for i in range(N):
    if visited[i]==1:continue
    visited[i]=1
    q.append([i,[i]])
    while q:
        n,c=q.pop()
        for j in F[n]:
            if visited[j]==0:
                c.append(j)
                visited[j]=1
                q.append([j,c])
    G.append(c)

for g in G:
    for i in g:
        for b in B[i]:
            if not  b in g:
                B[i].remove(b)

ans=[0]*N

for g in G:
    for i in g:
        cnt=0

        ans[i]=len(g)-len(F[i])-len(B[i])-1

for i in ans:
    print(str(i),end=" ")

Submission status: Wrong Answer

Solution code:
import copy
n,m,k = map(int,input().split())
ab = [[] for _ in range(n)]
for _ in range(m):
    a, b= (int(x) for x in input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
ans = []
#print(ab)
check = [0]*n
for i in range(n):
    check = [0]*n
    move = copy.copy(ab[i])
    check[i] = 1
    count = 0
    while len(move):
        j = move.pop(0)
        if check[j] == 0 :
            count += 1
            check[j] = 1
            for u in ab[j]:
                move.append(u)
    ans.append(count)          
            
for _ in range(k):
    c, d= (int(x) for x in input().split())
    if ans[c-1] == ans[d-1]:
        ans[c-1] -= 1
        ans[d-1] -= 1
for i in range(n):
    ans[i] -= len(ab[i])
#print(ans)
print(' '.join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
import copy
n,m,k = map(int,input().split())
ab = [[] for _ in range(n)]
for _ in range(m):
    a, b= (int(x) for x in input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
bl = [[] for _ in range(n)]
for _ in range(k):
    a, b= (int(x) for x in input().split())
    bl[a-1].append(b-1)
    bl[b-1].append(a-1)
ans = []
#print(ab)
#print(bl)
check = [0]*n
for i in range(n):
    check = [0]*n
    first = copy.copy(ab[i])
    #print(ab)
    #print(first)
    move = []
    check[i] = 1
    while len(first)>0:
        p = first.pop(0)
        check[p] = 1
        for q in ab[p]:
            #print(q)
            move.append(q)
    #print(move)
    count = 0
    while len(move):
        j = move.pop(0)
        if check[j] == 0 :
            check[j] = 1
            if j not in bl[i]:
                count += 1
            for k in ab[j]:
                move.append(k)
    ans.append(count)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys


class UnionFind():
    def __init__(self, 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


N, M, K = map(int, input().split())
IN = sys.stdin.readlines()
uf = UnionFind(N)
direct = [set() for _ in range(N)]
for c in IN[:N]:
    a, b = map(int, c.split())
    a -= 1; b -= 1
    uf.union(a, b)
    direct[a].add(b)
    direct[b].add(a)
print(uf.parents)
print(direct)
for c in IN[N:]:
    a, b = map(int, c.split())
    a -= 1; b -= 1
    if uf.find(a) == uf.find(b):
        direct[a].add(b)
        direct[b].add(a)
print(direct)
ans = []
for i in range(N):
    cnt = -uf.parents[uf.find(i)] - 1
    cnt -= len(direct[i])
    ans.append(cnt)

print(*ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Mar  2 06:12:32 2020

@author: naoki
"""
from collections import deque
import time
start = time.time()
time_all = []
#with open('C:/Users/naoki/Desktop/Atcoder/input.txt') as f:
#    N ,M ,K = map(int,f.readline().split())
#    A = [list(map(int,f.readline().split())) for _ in range(M)]
#    C = [list(map(int,f.readline().split())) for _ in range(K)]

N ,M ,K = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(M)]
C = [list(map(int,input().split())) for _ in range(K)]
connection = [[] for i in range(N)]
#seen = {i:False for i in range(1,N+1)}
seen = [False]*N
#label = {i:0 for i in range(1,N+1)}
label = [0]*N
todo = deque()
num = 0
#minus = {i:0 for i in range(1,N+1)}
minus = [0]*N 
for pair in A:
    connection[pair[0]-1] += [(pair[1]-1)]
    connection[pair[1]-1] += [(pair[0]-1)]
    minus[pair[0]-1] -= 1
    minus[pair[1]-1] -= 1
time_all.append(time.time()-start)

for k in range(N):
    if False not in seen:
        break
    num+=1
    H = seen.index(False)
    todo += [(H)]
    seen[H] = True
    group = []
    for j in range(N):
        if len(todo) <= 0:
            break
        current = todo.pop()
        label[current] = num
        group += [current]
        for i in connection[current]:
            if seen[i] == False:
                todo += [i]
                seen[i] = True
    #print(group)
time_all.append(time.time()-start)
for pair in C:
    if label[pair[0]-1] == label[pair[1]-1]:
        minus[pair[0]-1] -= 1
        minus[pair[1]-1] -= 1
accompany = {i:0 for i in range(1,num+1)}
for i in range(N):
    accompany[label[i]] += 1


print(" ".join(map(lambda x,y : str(accompany[x]+y-1), label, minus)))
#for i in range(N):
#    print(accompany[label[i]] + minus[i]-1)
time_all.append(time.time()-start)

print(time_all)

Submission status: Wrong Answer

Solution code:
import math
import itertools
import fractions
import heapq
import collections
import bisect
import sys
import copy

sys.setrecursionlimit(10**9)
mod = 10**7+9
inf = 10**20

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


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)


n,m,k = LI()

ab = [LI() for _ in range(m)]
cd = [LI() for _ in range(k)]
uf = UnionFind(n)

for a,b in ab:
    uf.union(a-1,b-1)
ans = [uf.size(i)-1 for i in range(n)]
print(uf.parents)
for a,b in ab:
    if uf.same(a-1,b-1):
        ans[a-1]-=1
        ans[b-1]-=1
for c,d in cd:
    if uf.same(c-1,d-1):
        ans[c-1]-=1
        ans[d-1]-=1

print(ans)

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 unite(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()}
n,m,k=map(int,input().split())
s=set()
uf=UnionFind(n+1)
r=set()
tree=[set() for i in range(n+1)]
for i in range(m):
  a,b=map(int,input().split())
  s.add((a,b))
  s.add((b,a))
  uf.unite(a,b)
  tree[a].add(b)
  tree[b].add(a)
for j in range(k):
  c,d=map(int,input().split())
  s.add((c,d))
  s.add((d,c))
  tree[c].add(d)
  tree[d].add(c)
for i in range(1,n+1):
  r.add(uf.find(i))
ans=[0]*(n+1)
for i in r:
  arr=uf.members(i)
  v=uf.size(i)
  for j in arr:
    ans[j]-=len(tree[j])
  for j in arr:
    ans[j]+=v-1
print(*ans[1:])

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self,size): 
        self.table = [-1 for _ in range(size)]
        self.cou = [1 for _ in range(size)]
    def find(self,x): 
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]
    def union(self,x,y): 
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] > self.table[s2]:
                self.table[s1] = s2
                self.cou[s2] += self.cou[s1]
                self.cou[s1] = 0
            elif self.table[s2] > self.table[s1]:
                self.table[s2] = s1
                self.cou[s1] += self.cou[s2]
                self.cou[s2] = 0
            else:
                self.table[s2] = s1
                self.table[s1] -= 1
                self.cou[s1] += self.cou[s2]
                self.cou[s2] = 0
        return
    
n, m, k = map(int, input().split())
BList = [[] for _ in range(n)]
friendU = UnionFind(n)
for i in range(m):
    a, b = map(int, input().split())
    BList[a-1].append(b-1)
    BList[b-1].append(a-1)
    friendU.union(a-1, b-1)

for i in range(k):
    c, d = map(int, input().split())
    if friendU.find(c-1) != friendU.find(d-1):
        BList[c-1].append(d-1)
        BList[d-1].append(c-1)
    
ansl = []
for i in range(n):
    j = friendU.find(i)
    ans = friendU.cou[j] - len(BList[i]) - 1
    ansl.append(ans)

print(*ansl)

Submission status: Wrong Answer

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

frends=[]
blocks=[]

for i in range(m):
    frend = sorted(list(map(int,input().split())))
    frends.append(frend)
for i in range(k):
    block=sorted(list(map(int,input().split())))
    blocks.append(block)
#print(frends)
#print(blocks)

a_relations = [0]*n
all_relations = []
for i in range(n):
    all_relations.append(a_relations.copy())
    all_relations[i][i] = 4
print(all_relations)

for element in frends:
    s = element[0]
    t = element[1]
    all_relations[s-1][t-1] = 1
    all_relations[t-1][s-1] = 1
print(all_relations)

for element in blocks:
    s = element[0]
    t = element[1]
    all_relations[s-1][t-1] = 2
    all_relations[t-1][s-1] = 2
print(all_relations)

for i in range(n):
    for j in range(n):
        if all_relations[i][j] == 0:
            for k in range(n):
                if k == i or k == j:
                    continue
                if all_relations[k][i] == 1 & all_relations[k][j] == 1:
                    all_relations[i][j] = 3
                    all_relations[j][i] = 3

#print(all_relations)

ans = []
for i in range(n):
    cnt = 0
    for j in range(n):
        if all_relations[i][j] == 3:
            cnt = cnt + 1
    ans.append(str(cnt))
            
#print(ans)
print(' '.join(ans))

Submission status: Wrong Answer

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

frends=[]
blocks=[]

for i in range(m):
    frend = sorted(list(map(int,input().split())))
    frends.append(frend)
for i in range(k):
    block=sorted(list(map(int,input().split())))
    blocks.append(block)
#print(frends)
#print(blocks)

a_relations = [0]*n
all_relations = []
for i in range(n):
    all_relations.append(a_relations.copy())
    all_relations[i][i] = 4
print(all_relations)

for element in frends:
    s = element[0]
    t = element[1]
    all_relations[s-1][t-1] = 1
    all_relations[t-1][s-1] = 1
print(all_relations)

for element in blocks:
    s = element[0]
    t = element[1]
    all_relations[s-1][t-1] = 2
    all_relations[t-1][s-1] = 2
print(all_relations)

for i in range(n):
    for j in range(n):
        if all_relations[i][j] == 0:
            for k in range(n):
                if k == i or k == j:
                    continue
                if all_relations[k][i] == 1 & all_relations[k][j] == 1:
                    all_relations[i][j] = 3
                    all_relations[j][i] = 3

print(all_relations)

ans = []
for i in range(n):
    cnt = 0
    for j in range(n):
        if all_relations[i][j] == 3:
            cnt = cnt + 1
    ans.append(str(cnt))
            
print(ans)
print(' '.join(ans))

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self,size): 
        self.table = [-1 for _ in range(size)]
        self.cou = [1 for _ in range(size)]
    def find(self,x): 
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]
    def union(self,x,y): 
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] > self.table[s2]:
                self.table[s1] = s2
                self.cou[s2] += self.cou[s1]
                self.cou[s1] = 0
            elif self.table[s2] > self.table[s1]:
                self.table[s2] = s1
                self.cou[s1] += self.cou[s2]
                self.cou[s2] = 0
            else:
                self.table[s2] = s1
                self.table[s1] -= 1
                self.cou[s1] += self.cou[s2]
                self.cou[s2] = 0
        return
    
n, m, k = map(int, input().split())
BList = [[] for _ in range(n)]
friendU = UnionFind(n)
for i in range(m):
    a, b = map(int, input().split())
    BList[a-1].append(b-1)
    BList[b-1].append(a-1)
    friendU.union(a-1, b-1)

for i in range(k):
    c, d = map(int, input().split())
    BList[c-1].append(d-1)
    BList[d-1].append(c-1)
    
ansl = []
for i in range(n):
    j = friendU.find(i)
    ans = friendU.cou[j] - len(BList[i]) - 1
    ansl.append(ans)

print(*ansl)

Submission status: Wrong Answer

Solution code:
class UnionFind:
  def __init__(self,n):
    self.par=[i for i in 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 union(self,x,y):
    x=self.find(x)
    y=self.find(y)
    if x==y:
      return
    if self.rank[x]<self.rank[y]:
      self.par[x]=y
      self.size[y]+=self.size[x]
    else:
      self.par[y]=x
      self.size[x]+=self.size[y]
      if self.rank[x]==self.rank[y]:
        self.rank[x]+=1
  def same(self,x,y):
    return self.find(x)==self.find(y)
  
N,M,K=map(int,input().split())
F=[[] for i in range(N)]
B=[[] for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  F[a].append(b)
  F[b].append(a)
for i in range(K):
  c,d=map(int,input().split())
  c,d=c-1,d-1
  F[c].append(d)
  F[d].append(c)    

UF=UnionFind(N)
for iam in range(N):
  for friend in F[iam]:
    UF.union(iam,friend)
ans=[UF.size[UF.find(iam)]-1 for iam in range(N)]
for iam in range(N):
  ans[iam]-=len(F[iam])
for iam in range(N):
  for block in B[iam]:
    if UF.same(iam,block):
      ans[iam]-=1
print(*ans,sep=' ')

Submission status: Wrong Answer

Solution code:
class UnionFind:
  def __init__(self,n):
    self.par=[i for i in 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 union(self,x,y):
    x=self.find(x)
    y=self.find(y)
    if x==y:
      return
    if self.rank[x]<self.rank[y]:
      self.par[x]=y
      self.size[y]+=self.size[x]
    else:
      self.par[y]=x
      self.size[x]+=self.size[y]
      if self.rank[x]==self.rank[y]:
        self.rank[x]+=1
  def same(self,x,y):
    return self.find(x)==self.find(y)
  
N,M,K=map(int,input().split())
F=[[] for i in range(N)]
B=[[] for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  F[a].append(b)
  F[b].append(a)
for i in range(K):
  c,d=map(int,input().split())
  c,d=c-1,d-1
  F[c].append(d)
  F[d].append(c)    

UF=UnionFind(N)
for iam in range(N):
  for friend in F[iam]:
    UF.union(iam,friend)
ans=[UF.size[UF.find(iam)]-1 for iam in range(N)]
for iam in range(N):
  ans[iam]-=len(F[iam])
for iam in range(N):
  for block in B[iam]:
    if UF.same(iam,friend):
      ans[iam]-=1
print(*ans,sep=' ')

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(2147483647)


class Graph:
    def __init__(self):
        self.graph = defaultdict(set)

    def interconnect(self, u, v):
        self.graph[u].add(v)
        self.graph[v].add(u)

    def dfs(self, start):
        seen = set()
        return self.dfs_recurse(start, seen)

    def dfs_recurse(self, v, seen):
        seen.add(v)
        for u in self.graph[v] - seen:
            self.dfs_recurse(u, seen)
        return seen


if __name__ == "__main__":
    n, m, k = map(int, input().split())

    friends = Graph()
    blocked = defaultdict(set)

    [friends.interconnect(*map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
    for _ in range(k):
        c, d = map(lambda x: int(x) - 1, input().split())
        blocked[c - 1].add(d)
        blocked[d - 1].add(c)

    visited = [False] * n
    counts = [0] * n

    for v in range(n):
        if visited[v]:
            continue
        elems = friends.dfs(v)
        elems_cnt = len(elems)
        for i in elems:
            counts[i] = elems_cnt - len(elems & friends.graph[i]) - len(elems & blocked[i]) - 1
            visited[i] = True

    print(*counts)

Submission status: Wrong Answer

Solution code:
import time, sys
sys.setrecursionlimit(int(1e7))

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

friends = [[] for i in range(n)]
cands = [None for i in range(n)]
cycles = []
visited = [False for i in range(n)]
count = [0 for i in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    friends[a].append(b)
    friends[b].append(a)

def dfs(x):
    visited[x] = True
    cycle.append(x)
    for i in friends[x]:
        if not visited[i]:
            dfs(i)
    return


for i, v in enumerate(visited):
    if v:
        continue
    cycle = []
    dfs(i)
    l = len(cycle)
    ind = len(cycles)
    cycles.append(cycle)
    for fr in cycle:
        cands[fr] = ind
        count[fr] = l - 1 - len(friends[fr])



for i in count:
    print(i, end=" ")

sys.exit(0)

for _ in range(k):
    a, b = map(lambda x: int(x)-1, input().split())
    if a in cycles[cands[b]]:
        count[a] -= 1
        count[b] -= 1

for i in count:
    print(i, end=" ")

Submission status: Wrong Answer

Solution code:
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)]

m1 = [[0]*n for _ in range(n)]
t1 = [[0]*n for _ in range(n)]
b1 = [[0]*n for _ in range(n)]

ans = [n-1]*n
for i in ab:
    i.sort()
    x,y = i
    t1[x-1][y-1] = 1
    t1[y-1][x-1] = 1

for i in cd:
    i.sort()
    x,y = i
    t1[x - 1][y - 1] = 1
    t1[y - 1][x - 1] = 1

for i,n1 in enumerate(t1):
    ans[i] -= sum(n1)

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

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(10**9)

N, M, K = map(int, input().split())
white = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(lambda s: int(s)-1, input().split())
    white[A].append(B)
    white[B].append(A)

black = [[] for _ in range(N)]
for _ in range(K):
    C, D = map(lambda s: int(s)-1, input().split())
    black[C].append(D)
    black[D].append(C)

ans = [False for _ in range(N)]

def freinds(i):
    visited = []

    Q = deque()
    Q.append(white[i])
    while Q:
        for q in Q.popleft():
            if q in visited:
                continue
            else:
                Q.append(white[q])
                visited.append(q)

    cnt = len(visited) - 1
    for v in visited:
        ans[v] = cnt    

for i in range(N):
    if ans[i]: continue
    else:
        # print(i) 
        freinds(i)

#print(ans)

for i in range(N):
    cnt = 0
    for b in black[i]:
        if ans[i] == ans[b]:
            cnt += 1
    black[i] = cnt

for i in range(N):
    ans[i] = ans[i] - len(white[i]) - black[i]

#print(ans, white, black)
print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(10**9)

N, M, K = map(int, input().split())
white = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(lambda s: int(s)-1, input().split())
    white[A].append(B)
    white[B].append(A)

black = [[] for _ in range(N)]
for _ in range(K):
    C, D = map(lambda s: int(s)-1, input().split())
    black[C].append(D)
    black[D].append(C)

ans = [False for _ in range(N)]

def freinds(i):
    visited = []

    Q = deque()
    Q.append(white[i])
    while Q:
        for q in Q.popleft():
            if q in visited:
                continue
            else:
                Q.append(white[q])
                visited.append(q)

    cnt = len(visited) - 1
    for v in visited:
        ans[v] = cnt    

for i in range(N):
    if ans[i]: continue
    else:
        print(i) 
        freinds(i)

Submission status: Wrong Answer

Solution code:
from collections import deque

N, M, K = map(int, input().split())
white = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(lambda s: int(s)-1, input().split())
    white[A].append(B)
    white[B].append(A)

black = [[] for _ in range(N)]
for _ in range(K):
    C, D = map(lambda s: int(s)-1, input().split())
    black[C].append(D)
    black[D].append(C)

ans = [False for _ in range(N)]

def freinds(i):
    visited = []

    Q = deque()
    Q.append(white[i])
    while Q:
        for q in Q.popleft():
            if q in visited:
                continue
            else:
                Q.append(white[q])
                visited.append(q)

    cnt = len(visited) - 1
    for v in visited:
        ans[v] = cnt    

for i in range(N):
    if ans[i]: continue
    else: freinds(i)

#print(ans)

for i in range(N):
    cnt = 0
    for b in black[i]:
        if ans[i] == ans[b]:
            cnt += 1
    black[i] = cnt

for i in range(N):
    ans[i] = ans[i] - len(white[i]) - black[i]

#print(ans, white, black)
print(*ans)

Submission status: Wrong Answer

Solution code:
def dfs(v, indirectly_connected, matrix, n, depth):
    if 2 <= depth:
        indirectly_connected[v] = True
    if not indirectly_connected[v]:
        for i in range(n):
            if indirectly_connected[i]:
                continue
            if matrix[v][i] or matrix[i][v]:
                dfs(i, indirectly_connected, matrix, n, (depth + 1))


n, m, k = map(int, input().split())
ab = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
cd = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(k)]
f_mat = [[False] * n for _ in range(n)]
b_mat = [[False] * n for _ in range(n)]
ans = []

for a, b in ab:
    for i in range(n):
        for j in range(n):
            f_mat[a][b] = True
            f_mat[b][a] = True
for c, d in cd:
    for i in range(n):
        for j in range(n):
            b_mat[c][d] = True
            b_mat[d][c] = True
for i in range(n):
    indirectly_connected = [False] * n
    dfs(i, indirectly_connected, f_mat, n, 0)
    tmp = 0
    for j in range(n):
        if (i != j) and \
          ((not f_mat[i][j]) and (not f_mat[j][i])) and \
          ((not b_mat[i][j]) and (not b_mat[j][i])) and \
          indirectly_connected[j]:
            tmp += 1
    ans.append(tmp)
print(" ".join(map(str, ans)))

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):
        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())
def solve():
  n,m,k = (int(i) for i in input().split())
  uff = UnionFind(n)
  ufb = UnionFind(n)
  query = [0]*n
  query2 = []
  for i in range(m):
    a,b = (int(i)-1 for i in input().split())
    uff.union(a,b)
    query[a] += 1
    query[b] += 1
    query2.append((a,b))
  for i in range(k):
    a,b = (int(i)-1 for i in input().split())
    if uff.same(a,b):
      ufb.union(a,b)
    query2.append((a,b))

  for i in range(n):
    print(uff.size(i)-1-query[i]-(ufb.size(i)-1), end=" ")
solve()

Submission status: Wrong Answer

Solution code:
N,M,K = map(int,input().split())
a = list()
ans = [N-1]*N
for i in range(M+K):
  a,b = map(int,input().split())
  for j in range(1,N+1):
    if a == j:
      ans[j-1] -= 1
    elif b == j:
      ans[j-1] -= 1
print(*ans)

Submission status: Wrong Answer

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

def main():
    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)]
    
    friend = [set() for i in range(N)]
    block = [set() for i in range(N)]
    root = [i for i in range(N)]
    
    for A, B in AB:
        A -= 1; B -= 1
        friend[A].add(B)
        friend[B].add(A)
    
        if A < B: a, b = A, B
        else: a, b = B, A
    
        while b != root[b]: b = root[b]
        while a != b: a, root[a] = root[a], b
        root[a] = b
        
    for C, D in CD:
        C -= 1; D -= 1
        block[C].add(D)
        block[D].add(C)
        
    g = [set() for i in range(N)]
    t = [i for i in range(N)]
    
    for i in range(N):
        r = i
        while r != root[r]: r = root[r]
        g[r].add(i)
        t[i] = r
        
    for i in range(N): print(max(0, len(g[t[i]] - friend[i] - block[i])-1))
        
if __name__ == '__main__':
    main()