Problem: 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?

Submission attempts (in order):
import sys
sys.setrecursionlimit(10**6)
N,M,K=map(int,input().split())
F=[[] for i in range(N)]
for _ in range(M):
    A,B=map(int,input().split())
    F[A-1].append(B-1)
    F[B-1].append(A-1)
B=[[] for i in range(N)]
for _ in range(K):
    C,D=map(int,input().split())
    B[C-1].append(D-1)
    B[D-1].append(C-1)
ans=[0 for i in range(N)]
seen=[False for i in range(N)]
n=0
G=[i for i in range(N)]
def root(i):
    if G[i]==i:
        return i
    else:
        a=root(G[i])
        G[i]=a
        return a
def union(i,j):
    x=root(i)
    y=root(j)
    if x==y:
        return
    else:
        if x>y:
            x,y=y,x
        G[y]=x
        return
for i in range(N):
    for f in F[i]:
        union(i, f)
group={}
for i in range(N):
    if G[i] in group:
        group[G[i]]+=1
    else:
        group[G[i]]=1
for i in range(N):
    ans=group[G[i]]
    for f in F[i]:
        if root(i)==root(f):
            ans-=1
    for b in B[i]:
        if root(i)==root(b):
            ans-=1
    print(ans-1, end=" ")

import sys
sys.setrecursionlimit(2000000)
N,M,K=map(int,input().split())
F=[set() for i in range(N)]
for _ in range(M):
    a,b=map(int,input().split())
    F[a-1].add(b-1)
    F[b-1].add(a-1)
B=[set() for i in range(N)]
for _ in range(K):
    c,d=map(int,input().split())
    B[c-1].add(d-1)
    B[d-1].add(c-1)

def dps(i, j, c):
    s=0
    con=False
    for f in F[j]:
        if f not in c:
            con=True
            break
    if not con:
        return 0
    for f in F[j]:
        if f in c:
            continue
        c.add(f)
        if f not in F[i] and f not in B[i]:
            s+=1
        s+=dps(i,f,c)
    return s
for i in range(0,N):
    checked=set()
    print(dps(i, i, checked)-1, end=" ")

import sys
sys.setrecursionlimit(2000000)
N,M,K=map(int,input().split())
F=[set() for i in range(N)]
for _ in range(M):
    a,b=map(int,input().split())
    F[a-1].add(b-1)
    F[b-1].add(a-1)
B=[set() for i in range(N)]
for _ in range(K):
    c,d=map(int,input().split())
    B[c-1].add(d-1)
    B[d-1].add(c-1)

def dps(i, j, c):
    s=0
    con=False
    for f in F[j]:
        if f not in c:
            con=True
            c.add(f)
            if f not in F[i] and f not in B[i]:
                s+=1
            s+=dps(i,f,c)
    if not con:
        return 0
    else:
        return s
for i in range(0,N):
    checked=set()
    print(dps(i, i, checked)-1, end=" ")

N,M,K=map(int,input().split())
F=[[] for i in range(N)]
for _ in range(M):
    A,B=map(int,input().split())
    F[A-1].append(B-1)
    F[B-1].append(A-1)
B=[[] for i in range(N)]
for _ in range(K):
    C,D=map(int,input().split())
    B[C-1].append(D-1)
    B[D-1].append(C-1)
ans=[0 for i in range(N)]
seen=[False for i in range(N)]
n=0
G=[i for i in range(N)]
def root(i):
    if G[i]==i:
        return i
    else:
        a=root(G[i])
        G[i]=a
        return a
def union(i,j):
    x=root(i)
    y=root(j)
    if x==y:
        return
    else:
        if x>y:
            x,y=y,x
        G[y]=x
        return
for i in range(N):
    for f in F[i]:
        union(i, f)
group={}
for i in range(N):
    if G[i] in group:
        group[G[i]]+=1
    else:
        group[G[i]]=1
for i in range(N):
    ans=group[G[i]]
    for f in F[i]:
        if root(i)==root(f):
            ans-=1
    for b in B[i]:
        if root(i)==root(b):
            ans-=1
    print(ans-1, end=" ")

import sys
sys.setrecursionlimit(2000000)
N,M,K=map(int,input().split())
F=[set() for i in range(N)]
for _ in range(M):
    a,b=map(int,input().split())
    F[a-1].add(b-1)
    F[b-1].add(a-1)
B=[set() for i in range(N)]
for _ in range(K):
    c,d=map(int,input().split())
    B[c-1].add(d-1)
    B[d-1].add(c-1)

def dps(i, j, c, fr, bl):
    s=0
    con=False
    for f in F[j]:
        if f not in c:
            con=True
            c.add(f)
            if f not in fr and f not in bl:
                s+=1
            s+=dps(i,f,c, fr, bl)
    if not con:
        return 0
    else:
        return s
for i in range(0,N):
    checked=set([i])
    print(dps(i, i, checked, F[i], B[i]), end=" ")


import sys
sys.setrecursionlimit(10**6)
N,M,K=map(int,input().split())
F=[[] for i in range(N)]
for _ in range(M):
    A,B=map(int,input().split())
    F[A-1].append(B-1)
    F[B-1].append(A-1)
B=[[] for i in range(N)]
for _ in range(K):
    C,D=map(int,input().split())
    B[C-1].append(D-1)
    B[D-1].append(C-1)
G=[i for i in range(N)]
def root(i):
    if G[i]==i:
        return i
    else:
        a=root(G[i])
        G[i]=a
        return a
def union(i,j):
    x=root(i)
    y=root(j)
    if x==y:
        return
    else:
        G[y]=x
        return
for i in range(N):
    for f in F[i]:
        union(i, f)
group={}
for i in range(N):
    if G[i] in group:
        group[G[i]]+=1
    else:
        group[G[i]]=1
for i in range(N):
    ans=group[G[i]]
    for f in F[i]:
        if root(i)==root(f):
            ans-=1
    for b in B[i]:
        if root(i)==root(b):
            ans-=1
    print(ans-1, end=" ")

import sys
sys.setrecursionlimit(2000000)
N,M,K=map(int,input().split())
F=[set() for i in range(N)]
for _ in range(M):
    a,b=map(int,input().split())
    F[a-1].add(b-1)
    F[b-1].add(a-1)
B=[set() for i in range(N)]
for _ in range(K):
    c,d=map(int,input().split())
    B[c-1].add(d-1)
    B[d-1].add(c-1)

def dps(i, j, c):
    s=0
    con=False
    for f in F[j]:
        if f not in c:
            con=True
            c.add(f)
            if f not in F[i] and f not in B[i]:
                s+=1
            s+=dps(i,f,c)
    if not con:
        return 0
    else:
        return s
for i in range(0,N):
    checked=set([i])
    print(dps(i, i, checked), end=" ")

import sys
sys.setrecursionlimit(2000000)
N,M,K=map(int,input().split())
F=[set() for i in range(N)]
for _ in range(M):
    a,b=map(int,input().split())
    F[a-1].add(b-1)
    F[b-1].add(a-1)
B=[set() for i in range(N)]
for _ in range(K):
    c,d=map(int,input().split())
    B[c-1].add(d-1)
    B[d-1].add(c-1)

def dps(i, j, c):
    s=0
    con=False
    for f in F[j]:
        if f not in c:
            con=True
            break
    if not con:
        return 0
    for f in F[j]:
        if f in c:
            continue
        c.add(f)
        if f not in F[i] and f not in B[i]:
            s+=1
        s+=dps(i,f,c)
    return s
print(F, B)
for i in range(0,N):
    checked=set()
    print(dps(i, i, checked)-1, end=" ")

N,M,K=map(int,input().split())
A=[];B=[]
for i in range(M):
    a,b=map(int,input().split())
    A.append(a);B.append(b)
C=[];D=[]
for i in range(K):
    c,d=map(int,input().split())
    C.append(c);D.append(d)
f=[set() for i in range(N)]
b=[set() for i in range(N)]
for i in range(M):
    f[A[i]-1].add(B[i]-1)
    f[B[i]-1].add(A[i]-1)
for i in range(K):
    b[C[i]-1].add(D[i]-1)
    b[D[i]-1].add(C[i]-1)
checked=[False for i in range(N)]
class UnionFind:
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
    def root(self,x):
        if self.parents[x]<0:
            return x
        else:
            self.parents[x]=self.root(self.parents[x])
            return self.parents[x]
    def union(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if x==y:
            return
        if self.parents[x]>self.parents[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
    def same(self,x,y):
        return self.root(x)==self.root(y)
    def size(self,x):
        return -self.parents[self.root(x)]
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x<0]
    def group_count(self):
        return len(self.roots())
uf=UnionFind(N)
for i in range(N):
    for people in f[i]:
        uf.union(i,people)
ans=[]
for i in range(N):
    c=uf.size(i)
    bl=0
    for x in b[i]:
        if uf.same(i,x):
            bl+=1
    ans.append(c-bl-1-len(f[i]))
print(*ans)

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Time Limit Exceeded

Wrong Answer

Time Limit Exceeded

Wrong Answer

Accepted