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: Runtime Error

Solution code:
import sys
readline = sys.stdin.buffer.readline
class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parent = [0] * (n+1)
        self.num = [1] * (n+1)
        self.diff_weight = [0] * (n+1)
        for i in range(n):
            self.parent[i] = i
    
    def root(self, x):
        if x == self.parent[x]:
            return x
        else:
            r = self.root(self.parent[x])
            self.diff_weight[r] += self.diff_weight[self.parent[x]]
            self.parent[x] = r
            return r
    
    def unite(self, a, b, w = 0):
        w += self.weight(a) - self.weight(b)
        a = self.root(a)
        b = self.root(b)
        if a == b:
            return
        self.parent[b] = a
        sum_v = self.num[a] + self.num[b]
        self.num[a] = sum_v
        self.num[b] = sum_v
        self.diff_weight[b] = w
        
    def same(self, a, b):
        return (self.root(a) == self.root(b))
    
    def sz(self, x):
        return self.num[self.root(x)]
    
    def weight(self, x):
        self.root(x)
        return self.diff_weight[x]

    def diff(self, a, b):
        return self.weight(b) - self.weight(a)


if __name__ == "__main__":

    N,M,K = map(int, readline().split())
    A = [0] * M
    B = [0] * M
    C = [0] * K
    D = [0] * K
    for i in range(M):
        a,b = map(int, readline().split())
        a -= 1
        b -= 1
        A[i] = a 
        B[i] = b 
    for i in range(K):
        a,b = map(int, readline().split())
        a -= 1
        b -= 1
        C[i] = a 
        D[i] = b 
    uf = UnionFind(100010)
    for i in range(M):
        uf.unite(A[i], B[i])

    arr = [[] for _ in range(N)]
    edge = [[] for _ in range(N)]
    for i in range(N):
        arr[uf.root(i)].append(i)
    
    for i in range(M):
        if uf.same(A[i], B[i]):
            edge[uf.root(A[i])].append(i)
    
    for i in range(K):
        if uf.same(C[i], D[i]):
            edge[uf.root(C[i])].append(i + M)
        

    ans = ["0"] * N
    for i in range(N):
        dd = {}
        if len(arr[i]) == 0:
            continue
        sz = uf.sz(i)
        for j, v in enumerate(arr[i]):
            dd[v] = j
        friends = [0] * sz
        for e in edge[i]:
            if e <= M-1:
                friends[dd[A[e]]] += 1
                friends[dd[B[e]]] += 1
            else:
                friends[dd[C[e-M]]] += 1
                friends[dd[D[e-M]]] += 1
        for v in arr[i]:
            res = sz - friends[dd[v]] - 1
            ans[v] = str(res)
    print(" ".join(ans))



    # for i in range(K):
    #     uf.unite(C[i], D[i])

    # friends = [0] * N 
    # block = [0] * N
    # for i in range(M):
    #     friends[A[i]] += 1
    #     friends[B[i]] += 1
    # for i in range(K):
    #     block[C[i]] += 1
    #     block[D[i]] += 1
    
    # ans = [] 
    # for i in range(N):
    #     res = uf.sz(i) - 1 - friends[i] - block[i]
    #     ans.append(str(res))
    # print(" ".join(ans))

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

con = defaultdict(list)
block = defaultdict(set)
friend = defaultdict(set)
for _ in range(M):
    A, B = list(map(int, input().split()))
    con[A].append(B)
    con[B].append(A)
    friend[A].add(B)
    friend[B].add(A)
for _ in range(K):
    C, D = list(map(int, input().split()))
    block[C].add(D)
    block[D].add(C)

visited = set()
group = defaultdict(set)

def dfs(node, visited, key):
    group[key].add(node)
    visited.add(node)
    for next in con[node]:
        if next not in visited:
            dfs(next, visited, key)


for i in range(1, N + 1):
    dfs(i, visited, i)

ret = [0 for i in range(N)]
for g in group.values():
    size = len(g)
    for node in g:
        exclude = 0
        for blocked in block[node]:
            if blocked in g:
                exclude += 1
        for friended in friend[node]:
            if friended in g:
                exclude += 1
        # print("node = " + str(node - 1) + " " + str(size - exclude - 1))
        ret[node - 1] = max(ret[node - 1], size - exclude - 1)

print(' '.join([str(s) for s in ret]))

Submission status: Runtime Error

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


class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]

    def root(self, x):
        if self.parent[x] == x:
            return(x)
        else:
            self.parent[x] = self.root(self.parent[x])
            return(self.parent[x])

    def same(self, x, y):
        x, y = x-1, y-1
        return(self.root(x) == self.root(y))

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            return


N, M, K = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(M)]

CD = [tuple(map(int, input().split())) for i in range(K)]

tableF = collections.defaultdict(set)
tableB = collections.defaultdict(set)


for c, d in CD:
    tableB[c].add(d)
    tableB[d].add(c)

G = unionFind(N)
for a, b in AB:
    G.unite(a, b)
    tableF[a].add(b)
    tableF[b].add(a)

for i in range(N):
    tableF[i+1].add(i+1)


F = collections.defaultdict(set)
ans = [0]*N
for i in range(N):
    F[G.root(i)].add(i+1)

for i in range(N):
    ans[i] = len(F[G.root(i)] - tableB[i+1] - tableF[i+1])

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

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

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

def dfs(u):
    if visited[u]:
        return

    visited[u] = True

    for v in graph[u]:
        s.add(v)
        dfs(v)

graph = {}

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1

    graph[a] = graph.get(a, set())
    graph[a].add(b)

    graph[b] = graph.get(b, set())
    graph[b].add(a)

blocks = {}

for _ in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1

    blocks[c] = blocks.get(c, set())
    blocks[c].add(d)

    blocks[d] = blocks.get(d, set())
    blocks[d].add(c)

ans = [0] * n

visited = [False] * n

for u in range(n):
    if not visited[u]:
        s = set()

        dfs(u)

        l = len(s)

        for i in s:
            ans[i] += l - 1

            if i in blocks:
                ans[i] -= len(blocks[i].intersection(s))

            if i in graph:
                ans[i] -= len(graph[i].intersection(s))

print(*ans)

Submission status: Runtime Error

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

def dfs(u):
    if visited[u]:
        return

    visited[u] = True

    for v in graph[u]:
        s.add(v)
        dfs(v)

graph = {}

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1

    graph[a] = graph.get(a, set())
    graph[a].add(b)

    graph[b] = graph.get(b, set())
    graph[b].add(a)

blocks = {}

for _ in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1

    blocks[c] = blocks.get(c, set())
    blocks[c].add(d)

    blocks[d] = blocks.get(d, set())
    blocks[d].add(c)

ans = [0] * n

visited = [False] * n

for u in range(n):
    if not visited[u]:
        s = set()

        dfs(u)

        l = len(s)

        for i in s:
            ans[i] += l - 1

            if i in blocks:
                ans[i] -= len(blocks[i].intersection(s))

            if i in graph:
                ans[i] -= len(graph[i].intersection(s))

print(*ans)

Submission status: Runtime Error

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

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

def dfs(start, i):
	visited[i] = 1
	for adj in friend[i]:
		if visited[adj]: continue
		if not adj in friend[start] and not adj in block[start]:
			ans[start] += 1
		dfs(start, adj)
		
	
for i in range(N):
	visited = [0] * N
	dfs(i, i)
	
print(*ans)

Submission status: Runtime Error

Solution code:
class uni:
    def __init__(self,n):
        self.n = n
        self.pare = [i for i in range(n)]

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

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

    def show(self):
        return self.pare


N, M, K = map(int,input().split())
size = [0]*N
count = [0]*N
side = [[]for i in range(N)]
union = uni(N)
for i in range(M):
    a,b = map(int,input().split())
    union.union(a-1,b-1)
    count[a-1] += 1
    count[b-1] += 1
for i in range(N):
    size[union.find(i)] += 1
for i in range(K):
    c,d = map(int,input().split())
    if union.pare[c-1] == union.pare[d-1]:
        count[c-1] += 1
        count[d-1] += 1
for i in range(N):
    print(size[union.pare[i]]-count[i]-1,end=" ")
print()

Submission status: Runtime Error

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


class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]

    def root(self, x):
        if self.parent[x] == x:
            return(x)
        else:
            self.parent[x] = self.root(self.parent[x])
            return(self.parent[x])

    def same(self, x, y):
        x, y = x-1, y-1
        return(self.root(x) == self.root(y))

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            return


N, M, K = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(M)]

CD = [tuple(map(int, input().split())) for i in range(K)]

tableF = collections.defaultdict(set)
tableB = collections.defaultdict(set)


for c, d in CD:
    tableB[c].add(d)
    tableB[d].add(c)


G = unionFind(N)
for a, b in AB:
    G.unite(a, b)
    tableF[a].add(b)
    tableF[b].add(a)

for i in range(N):
    tableF[i+1].add(i+1)


F = collections.defaultdict(set)
ans = [0]*N
for i in range(N):
    F[G.root(i)].add(i+1)
for i in range(N):
    ans[i] = len(F[G.parent[i]] - tableB[i+1] - tableF[i+1])

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

Submission status: Runtime Error

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

class UnionFind:
	def __init__(self, n):
		self.groups = [g for g in range(n)]

	def get_root(self, i):
		parent = self.groups[i]
		if parent == i:
			return parent
		else:
			root = self.get_root(parent)
			self.groups[i] = root
			return root
	
	def set_root(self, i, root):
		parent = self.groups[i]
		self.groups[i] = root
		if parent == i:
			return
		else:
			self.set_root(parent, root)
	
	def combine(self, i1, i2):
		self.set_root(i2, self.get_root(i1))
	
	def in_same_group(self, i1, i2):
		return self.get_root(i1) == self.get_root(i2)
	
	def to_dic(self):
		table = {}
		for i in range(len(self.groups)):
			g = self.get_root(i)
			if g in table:
				table[g].add(i)
			else:
				table[g] = {i}
		
		ret = [None] * len(self.groups)
		
		for t in table.values():
			for i in t:
				ret[i] = t
		
		return ret
	
	def to_list(self):
		table = self.to_dic()
		return [table[g] for g in table]


groups = UnionFind(N)

blocks = [set() for _ in range(N)]

for _ in range(M):
	a, b = map(int, input().split())
	groups.combine(a - 1, b - 1)
	blocks[a - 1].add(b - 1)
	blocks[b - 1].add(a - 1)

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

groups = groups.to_dic()

print(" ".join((str(len(groups[i] - blocks[i]) - 1) for i in range(N))))

Submission status: Runtime Error

Solution code:
//#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
using namespace std;
//using namespace __gnu_pbds;
//template <class c, class cmp = less<c> > using ordered_set = tree<c, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;



  #define IOS ios_base::sync_with_stdio(false);cin.tie(NULL); 

  #define ff first
  #define ss second
  #define pb push_back
  #define pf push_front
  #define mp make_pair
  #define in insert
  #define ld long double


  #define TRACE
  #ifdef TRACE
  #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  template <typename Arg1>
  void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << std::endl;
  }
  template <typename Arg1, typename... Args>
  void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  }
  #else
  #define trace(...) 1
  #endif
  template<class T> ostream& operator<<(ostream &os, vector<T> V) {os << "[ "; for(auto v : V) os << v << " "; return os << "]";}
  template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {return os << "(" << P.first << "," << P.second << ")";}
  template <typename T,typename U>pair<T,U> operator+(const pair<T,U> & l,const std::pair<T,U> & r) { return {l.first+r.first,l.second+r.second};}
  typedef long long int ll;

  typedef vector<int> vi;
  typedef vector<ll> vl;
  typedef vector<vi> vvi;
  typedef vector<vl> vvl;
  typedef pair<int,int> pii;
  typedef pair<ll,ll> pll;
  typedef vector<pii> vpii;
  typedef vector<pll> vpll;
  const ll mod =1e9+7;
  const ll MAX_NODES =200001;
  const ll MAX_LOG =50;
  const ll maxn = 400000+10;
  #define endl '\n'
  ll power(ll x, ll n) {
      ll res = 1;
      for (; n > 0; n >>= 1) {
      if (n & 1) res = (res * x) % mod;
      x = (x * x) % mod;
      }
      return res;
  }
  struct DSU{
    vector<int >par,sz;
    DSU(int n)
    {
      par.resize(n);
      sz = vi(n,1);
      iota(par.begin(),par.end(),0);
    }
    int find(int  x){
        if(x==par[x])
          return x;
        return par[x] = find(par[x]);
    }
    void unite(int  a, int  b){
        a = find(a);
        b = find(b);
        if(a==b)
          return ;
        if(sz[a]<sz[b])
          swap(a,b);
        par[b] = a;
        sz[a]+=sz[b];
        return ;
    }

  };
int main()
{

	IOS
	int n,m,k;
	cin>>n>>m>>k;
	DSU fr(n);
	vector<int> g[n],g1[n];
	for(ll i = 0;i<m;i++)
	{
		ll u,v;
		cin>>u>>v;
		u--,v--;
		g[u].pb(v);
		g[v].pb(u);
		fr.unite(u,v);
	}
	for(ll i = 0;i<k;i++)
	{
		ll u,v;
		cin>>u>>v;
		u--,v--;
		g1[u].pb(v);
		g1[v].pb(u);
	}
	for(ll i= 0;i<n;i++)
	{
		int ans = fr.sz[fr.find(i)] - g[i].size()-1;
		for(auto x:g1[i])
		{
			if(fr.find(i) == fr.find(x))
			{
				ans--;
			}
		}
		cout<<ans<<" ";
	}
	


}

Submission status: Runtime Error

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

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

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

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
N,M,K = map(int,input().split())
uf = UnionFind(N+1)
d = [0 for i in range(N+1)]
F = []
B = [[0 for i in range(N+1)] for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    uf.union(a,b)
    d[a] -= 1
    d[b] -= 1
for i in range(1,N+1):
    n = len(uf.members(i))
    d[i] += n - 1
for j in range(K):
    a,b = map(int,input().split())
    if uf.same(a,b):
        d[a] -= 1
        d[b] -= 1
d.pop(0)
for i in range(N):
    d[i] = str(d[i])
d = ' '.join(d)
print(d)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n, m, k = map(int,input().split())
A = [list(map(int,input().split())) for i in range(m)]
B = [list(map(int,input().split())) for i in range(k)]

for i in range(m):
    for j in range(2):
        A[i][j] -= 1
for i in range(k):
    for j in range(2):
        B[i][j] -= 1


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 size(self, x):
        if self.parents[x] < 0:
            return -self.parents[x]
        else:
            self.parents[x] = self.size(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 n_cc(self):  # 連結成分の数
        A = [i for i in self.parents if i < 0]
        return len(A)

U = UnionFind(n)
for i in range(m):
    a = A[i][0]
    b = A[i][1]
    U.union(a, b)
C = [0] * n

for i in range(m):
    a = A[i][0]
    b = A[i][1]
    C[a] -= 1
    C[b] -= 1
for i in range(k):
    a = B[i][0]
    b = B[i][1]
    if U.find(a) == U.find(b):
        C[a] -= 1
        C[b] -= 1
# print(C)
ANS = []
for i in range(n):
    ANS.append(U.size(i) + C[i] - 1)
print(" ".join([str(i) for i in ANS]))

Submission status: Runtime Error

Solution code:
import collections

class UnionFind:

    def __init__(self, N):
        self.raw = [i for i in range(N)]

    def root(self, i):
        if self.raw[i] == i:
            return i
        self.raw[i] = self.root(self.raw[i])
        return self.raw[i]

    def unite(self, a, b):
        a_root = self.root(a)
        b_root = self.root(b)
        self.raw[a_root] = b_root

    def is_same(self, a, b):
        return self.root(a) == self.root(b)


def solve(N, M, K, AB, CD):
    uf = UnionFind(N)
    minus_count = [0 for _ in range(N)]
    for a, b in AB:
        uf.unite(a - 1, b - 1)
        minus_count[a - 1] += 1
        minus_count[b - 1] += 1
    for c, d in CD:
        if uf.is_same(c - 1, d - 1):
            minus_count[c - 1] += 1
            minus_count[d - 1] += 1
    counter = collections.Counter()
    roots = [uf.root(i) for i in range(N)]
    counter.update(roots)

    ans = []
    for i in range(N):
        ans.append(str(counter[uf.root(i)] - minus_count[i] - 1))
    return " ".join(ans)

if __name__ == "__main__":
    N, M, K = tuple(map(int, input().split(" ")))
    AB = []
    for _ in range(M):
        AB.append(tuple(map(int, input().split(" "))))
    CD = []
    for _ in range(K):
        CD.append(tuple(map(int, input().split(" "))))
    print(solve(N, M, K, AB, CD))

Submission status: Runtime Error

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

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

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

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
uf = UnionFind(N+1)
N,M,K = map(int,input().split())
d = [0 for i in range(N+1)]
F = []
B = [[0 for i in range(N+1)] for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    uf.union(a,b)
    d[a] -= 1
    d[b] -= 1
for i in range(1,N+1):
    n = len(uf.members(i))
    d[i] += n
for j in range(K):
    a,b = map(int,input().split())
    if uf.same(a,b):
        d[i] -= 1
d.pop(0)
for i in range(N):
    d[i] = str(d[i])
d = ' '.join(d)
print(d)