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

Solution (Python):
n,m,k = map(int,input().split())
A = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    A[a].append(b)
    A[b].append(a)
C = [[] for i in range(n+1)]
for i in range(k):
    c,d = map(int,input().split())
    C[c].append(d)
    C[d].append(c)
from collections import deque
reach = [0]*(n+1)
for i in range(1,n+1):
    if reach[i] != 0:
        pass
    else:
        reach[i] = i
        q = deque([])
        q.append(i)
        while q:
            x = q.popleft()
            for s in A[x]:
                if reach[s] == 0:
                    q.append(s)
                    reach[s] = i
dis_count = [0]*(n+1)
for i,C0 in enumerate(C):
    for CC in C0:
        if reach[CC] == reach[i]:
            dis_count[i] += 1
import collections
D = collections.Counter(reach)
for i in range(1,n+1):
    print(D[reach[i]]-len(A[i])-dis_count[i]-1,end="")
    print(" ",end="")
print("")

Solution (Python):
import sys
input = sys.stdin.readline
n, m, k = map(int, input().split())

friend = [0] * n
block = [0] * n

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

uf = UnionFind(n)
ab = [list(map(int, input().split())) for i in range(m)]
for a, b in ab:
    uf.union(a-1, b-1)
    friend[a-1]+=1
    friend[b-1]+=1

for i in range(k):
    c, d = map(int, input().split())
    if uf.same(d-1, c-1):
        block[c-1]+=1
        block[d-1]+=1

ans = []
for i in range(n):
    ans.append(uf.size(i) - friend[i] - block[i] -1 )
print(' '.join(list(map(str, ans))))

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m,k = map(int, input().split())
class UnionFindTree:
    def __init__(self, n):
        self.n = n
        self.parent = list(range(n))
        self.size = [1] * n

    def root(self, i):
        inter = set()
        while self.parent[i]!=i:
            inter.add(i)
            i = self.parent[i]
        r = i
        for i in inter:
            self.parent[i] = r
        return r

    def connect(self, i, j):
        if i==j:
            return
        ri = self.root(i)
        rj = self.root(j)
        if ri==rj:
            return
        if self.size[ri]<self.size[rj]:
            self.parent[ri] = rj
            self.size[rj] += self.size[ri]
        else:
            self.parent[rj] = ri
            self.size[ri] += self.size[rj]
    
uf = UnionFindTree(n)
ns = [[] for _ in range(n)]
for i in range(m):
    a,b = map(lambda x: int(x)-1, input().split())
    uf.connect(a,b)
    ns[a].append(b)
    ns[b].append(a)

for i in range(k):
    c,d = map(lambda x: int(x)-1, input().split())
    ns[c].append(d)
    ns[d].append(c)
    
ans = [None]*n
for i in range(n):
    r = uf.root(i)
    s = uf.size[r]
    v = 0
    for j in ns[i]:
        if r==uf.root(j):
            v += 1
    ans[i] = s - v - 1
write(" ".join(map(str, ans)))

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

class UnionFind:
    def __init__(self, N):
        self.root = list(range(N + 1))
        self.size = [1] * (N + 1)

    def __getitem__(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    def merge(self, x, y):
        x = self[x]
        y = self[y]
        if x == y:
            return
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            x, y = y, x
            sx, sy = sy, sx
        self.root[y] = x
        self.size[x] += sy

def graph_input(N, M):
    G = [[] for _ in range(N + 1)]
    for _ in range(M):
        a, b = map(int, readline().split())
        G[a].append(b)
        G[b].append(a)
    return G

N, M, K = map(int, readline().split())
friend = graph_input(N, M)
block = graph_input(N, K)

uf = UnionFind(N + 1)
for a in range(N + 1):
    for b in friend[a]:
        uf.merge(a, b)

answer = [0] * (N + 1)
for a in range(N + 1):
    n = uf.size[uf[a]] - 1
    for x in friend[a] + block[a]:
        if uf[a] == uf[x]:
            n -= 1
    answer[a] = n

print(' '.join(map(str, answer[1:])))

Solution (Python):
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 blocks[i]:
        if ins_friend.find(i, x) == True:
            ans[i] -= 1
print(*ans)

Solution (Python):
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 blocks[i]:
        if ins_friend.find(i, x) == True:
            ans[i] -= 1
print(*ans)

Solution (Python):


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 = map(int, input().split())
par = [-1]*N

num = [0]*N

uf = UnionFind(N)

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    
    uf.union(a, b)
    
    num[a] += 1
    num[b] += 1

for _ in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    
    
    if uf.same(c, d):
        num[c] += 1
        num[d] += 1

for i in range(N):
    
    print(uf.size(i)-1-num[i], end=" ")

Solution (Python):
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 size(x):
        return -par[find(x)]

    n, m, k = map(int, input().split())
    par = [-1] * n
    r = [-1] * n
    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        unite(a, b)
        r[a] -= 1
        r[b] -= 1
    for i1 in range(n):
        r[i1] += size(i1)
    m = map(int, read().split())
    cd = zip(m, m)
    for c, d in cd:
        c -= 1
        d -= 1
        if same(c, d):
            r[c] -= 1
            r[d] -= 1
    print(*r, end=' ')

if __name__ == '__main__':
    main()

Solution (Python):

from sys import setrecursionlimit


def find(parent, i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, t)
    parent[i] = t
    return t


def unite(parent, i, j):
    i = find(parent, i)
    j = find(parent, j)
    if i == j:
        return
    parent[j] += parent[i]
    parent[i] = j


setrecursionlimit(10 ** 6)


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

parent = [-1] * N
friends = [[] for _ in range(N)]
for A, B in AB:
    unite(parent, A - 1, B - 1)
    friends[A-1].append(B-1)
    friends[B-1].append(A-1)
blocks = [[] for _ in range(N)]
for C, D in CD:
    blocks[C-1].append(D-1)
    blocks[D-1].append(C-1)

result = []
for i in range(N):
    p = find(parent, i)
    t = -parent[p] - 1
    t -= len(friends[i])
    for b in blocks[i]:
        if p == find(parent, b):
            t -= 1
    result.append(t)
print(*result)

Solution (Python):
def main():
    from collections import deque
    N, M, K = map(int, input().split())
    f = [set() for _ in range(N + 1)]
    b = [set() for _ in range(N + 1)]

    for _ in range(M):
        i, j = map(int, input().split())
        f[i].add(j)
        f[j].add(i)
    for _ in range(K):
        i, j = map(int, input().split())
        b[i].add(j)
        b[j].add(i)
    
    visited = [False] * (N + 1)
    ans = [0] * (N + 1)

    for i in range(1, N+1):
        if visited[i]:
            continue
        visited[i] = True
        link = {i}
        todo = deque([i])
        while len(todo) != 0:
            c = todo.pop()
            for p in f[c]:
                if not(visited[p]):
                    link.add(p)
                    todo.append(p)
                    visited[p] = True
        for j in link:
            ans[j] = len(link) - len(link & f[j]) - len(link & b[j]) - 1
    
    print(*ans[1:])

if __name__ == '__main__':
    main()

Solution (Python):


import sys
input=sys.stdin.readline
from collections import deque

def main():
    N,M,K=map(int,input().split())
    ABadj=[[] for i in range(N)]
    CDadj=[set() for i in range(N)]
    for i in range(M):
        a,b=map(int,input().split())
        ABadj[a-1].append(b-1)
        ABadj[b-1].append(a-1)
    for i in range(K):
        c,d=map(int,input().split())
        CDadj[c-1].add(d-1)
        CDadj[d-1].add(c-1)
    
    w=[-1]*N
    sets=[]
    j=-1
    done=[-1]*N
    for i in range(N):
        if done[i]==-1:
            sets.append(set())
            j+=1
            qu=deque([i])
            done[i]=1
            sets[j].add(i)
            w[i]=j
            while(len(qu)>0):
                v=qu.popleft()
                for nv in ABadj[v]:
                    if done[nv]==-1:
                        done[nv]=1
                        qu.append(nv)
                        sets[j].add(nv)
                        w[nv]=j
    
    for i in range(N):
        ans=len(sets[w[i]])-1-len(ABadj[i])
        for bl in CDadj[i]:
            if bl in sets[w[i]]:
                ans-=1
        print(ans,end=" ")
            
    
    
    
if __name__=="__main__":
    main()

Solution (Python):







inp = input
MAXX = 10**5 + 5

def bfs(NN, adj, visited, node, comp, ncomp):
    compsize = 0
    while len(node) > 0:
        newnode = []
        for n in node:
            comp[n] = ncomp
            compsize += 1
            for a in adj[n]:
                if visited[a] == False:
                    visited[a] = True
                    newnode.append(a)
        node = newnode

    return compsize



N, M, K = map(int, inp().split())
adj = [[] for _ in range(N+1)]
nfriend = [0]*(N+1)
nblock = [0]*(N+1)
for m in range(M):
    a, b, = map(int, inp().split())
    adj[a].append(b)
    adj[b].append(a)
    nfriend[a] += 1
    nfriend[b] += 1

comp = [0]*(N+1)
compsize = [0]
ncomp = 0
visited = [False]*(N+1)

for n in range(1, N+1):
    if comp[n] <= 0:
        visited[n] = True
        csize = bfs(N, adj, visited, [n], comp, ncomp+1)
        if csize > 0:
            ncomp += 1
            compsize.append(csize)

for k in range(K):
    c, d = map(int, inp().split())
    if comp[c] == comp[d]:
        nblock[c] += 1
        nblock[d] += 1

ans = ""
for n in range(1, N+1):
    can = compsize[comp[n]] - nfriend[n] - nblock[n] - 1
    ans += str(can)
    if n == N:
        ans += "\n"
    else:
        ans += " "

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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 same(self, x, y):
        return self.find(x) == self.find(y)

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


def resolve():
    n, m, k = map(int, input().split())
    uf = UnionFind(n)
    edge = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        uf.union(a - 1, b - 1)
        edge[a - 1].append(b - 1)
        edge[b - 1].append(a - 1)

    block = [[] for _ in range(n)]
    for _ in range(k):
        c, d = map(int, input().split())
        if uf.same(c - 1, d - 1):
            block[c - 1].append(d - 1)
            block[d - 1].append(c - 1)

    res = []
    for i in range(n):
        res.append(uf.size(i) - (len(edge[i]) + 1) - (len(block[i])))
    print(*res)


if __name__ == '__main__':
    resolve()

Solution (Python):
class Union_Find():
    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=map(int,input().split())

A=[set() for _ in range(N+1)]
U=Union_Find(N+1)
for _ in range(M):
    a,b=map(int,input().split())
    A[a].add(b)
    A[b].add(a)
    U.union(a,b)

C=[set() for _ in range(N+1)]
for _ in range(K):
    c,d=map(int,input().split())
    C[c].add(d)
    C[d].add(c)

S=[]
for k in range(1,N+1):
    t=U.size(k)
    for a in C[k]:
        if U.find(a)==U.find(k):
            t-=1

    t-=len(A[k])
    S.append(t-1)

print(" ".join(map(str,S)))

Solution (Python):
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 = map(int, input().split())

ndic = {i:set() for i in range(1,N+1)}
bdic = {i:set() for i in range(1,N+1)}

uf = UnionFind(N+1)
rlt = []

for _ in range(M):
  a,b = map(int, input().split())
  ndic[a].add(b)
  ndic[b].add(a)
  uf.union(a,b)
  
for _ in range(K):
  a,b = map(int, input().split())
  bdic[a].add(b)
  bdic[b].add(a)
  
for i in range(1,N+1):
  tmp = uf.size(i)
  for a in bdic[i]:
    if uf.find(a) == uf.find(i):
      tmp -= 1
  tmp -= len(ndic[i])
  rlt.append(tmp-1)
  
print(" ".join(map(str, rlt)))

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

par=[-1]*N
num=[0]*N

def find(x):
    if par[x]<0:
        return x
    else:
        par[x]=find(par[x])
        return par[x]

def union(x,y):
    p,q=find(x),find(y)
    if p==q:
        return
    if p>q:
        p,q=q,p
    par[p]+=par[q]
    par[q]=p   

def size(x):
    return -par[find(x)]

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

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

for _ in range(K):
    c,d=map(int,input().split())
    c-=1
    d-=1
    if same(c,d):
        num[c]+=1
        num[d]+=1

for i in range(N):
    print(size(i)-1-num[i],end=" ")

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.ps = [-1] * (n + 1)

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.ps[x] > self.ps[y]:
            x, y = y, x
        self.ps[x] += self.ps[y]
        self.ps[y] = x
        return True

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

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


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


uf = UnionFind(n)

friends = [0] * (n + 1)
chain = [0] * (n + 1)

for _ in range(m):
    a, b = map(int, input().split())
    friends[a] += 1
    friends[b] += 1
    uf.union(a, b)

for _ in range(k):
    c, d = map(int, input().split())
    if uf.same(c, d):
        friends[c] += 1
        friends[d] += 1

ans = []
for i in range(1, n + 1):
    ans.append(uf.size(i) - friends[i] - 1)

print(*ans)

Solution (Python):
def main():
    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 other_members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root and i != x]

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

        def __str__(self):
            return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

    import sys
    def input():
        return sys.stdin.readline().rstrip()
    n, m, k = list(map(int, input().split()))
    uf = UnionFind(n)
    counts = [0] * n
    for _ in range(m):
        a, b = list(map(lambda x: int(x) - 1, input().split()))
        uf.union(a, b)
        counts[a] += 1
        counts[b] += 1
    for _ in range(k):
        c, d = list(map(lambda x: int(x) - 1, input().split()))
        if uf.same(c, d):
            counts[c] += 1
            counts[d] += 1
    print(' '.join([str(uf.size(i) - counts[i] - 1) for i in range(n)]))

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

n, m, k = map(int, input().split())
F = [[] for i in range(n)]
B = [[] for i in range(n)]
l = [0]*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):
    c, d = map(int, input().split())
    B[c - 1].append(d - 1)
    B[d - 1].append(c - 1)

seen = [0]*n
cnt = 0
r = []

def dfs(x):
    if seen[x] == 0:
        r[cnt].add(x)
        seen[x] = 1
        for i in F[x]:
            dfs(i)

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

ans = [0]*n

for i in r:
    lr = len(i)
    for j in i:
        ans[j] = lr - len(F[j]) - len(i & set(B[j])) - 1

print(*ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

n, m, k = map(int, input().split())
F = [[] for i in range(n)]
B = [set() for i in range(n)]
l = [0]*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):
    c, d = map(int, input().split())
    B[c - 1].add(d - 1)
    B[d - 1].add(c - 1)

seen = [0]*n
cnt = 0
r = []

def dfs(x):
    if seen[x] == 0:
        r[cnt].add(x)
        seen[x] = 1
        for i in F[x]:
            dfs(i)

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

ans = [0]*n

for i in r:
    lr = len(i)
    for j in i:
        ans[j] = lr - len(F[j]) - len(i & B[j]) - 1

print(*ans)

Solution (Python):
N,M,K = map(int,input().split())
fr = [[] for i in range(N+1)]
bl = [[] for i in range(N+1)]
for _ in range(M):
    A,B = map(int, input().split())
    fr[A].append(B)
    fr[B].append(A)
for _ in range(K):
    C,D = map(int, input().split())
    bl[C].append(D)
    bl[D].append(C)

leader = [0]*(N+1)
d = {}
for root in range(1,N+1):
    if leader[root]!=0:
        continue
    d[root] = set([root])
    stack = [root]
    while stack:
        start = stack.pop()
        leader[start] = root
        for v in fr[start]:
            if leader[v]!=0:
                continue
            d[root].add(v)
            stack.append(v)

ans = [0]*(N+1)
for i in range(1,N+1):
    cluster = d[leader[i]]
    ans[i] = len(cluster) - len(fr[i]) - 1
    for b in bl[i]:
        if b in cluster:
            ans[i] -= 1
print(*ans[1:])

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

    @staticmethod
    def fact(N):
        res = {}
        tmp = N
        for i in range(2, int(N ** 0.5 + 1) + 1):
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if cnt > 0:
                res[i] = cnt
        if tmp != 1:
            res[tmp] = 1
        if res == {}:
            res[N] = 1
        return res


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


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 unite(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 size(self, x):
        return -self.parents[self.root(x)]

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


def solve():
    N, M, K = Scanner.map_int()
    uni = UnionFind(N)
    friends = [set() for _ in range(N)]
    for _ in range(M):
        a, b = Scanner.map_int()
        a -= 1
        b -= 1
        uni.unite(a, b)
        friends[a].add(b)
        friends[b].add(a)
    block = [set() for _ in range(N)]
    for _ in range(K):
        a, b = Scanner.map_int()
        a -= 1
        b -= 1
        block[a].add(b)
        block[b].add(a)
    ans = [0 for _ in range(N)]
    for i in range(N):
        size = uni.size(i)
        f = len(friends[i])
        bn = 0
        for b in block[i]:
            if uni.is_same(i, b):
                bn += 1
        ans[i] = size - 1 - f - bn
    print(*ans)


def main():
    
    
    
    
    
    solve()


if __name__ == "__main__":
    main()