1816. 潜在好友数
时间限制：1000 MS 内存限制：128 MB
题目描述
## 题目描述 假设你正在开发一个社交网络 ${APP}$，这个${APP}$暂时还没有上线，但是为了测试${APP}$ 功能的完善性，现在导入了 ${n}$ 个内测用户。 在这 $n$ 个用户之间，有 ${m}$ 组朋友关系以及 ${k}$ 组仇敌关系。 现在你要测试的是潜在好友功能：假如现在有 ${a,b,c}$ 三个用户， ${a}$ 和 ${b}$ 是朋友，${b}$ 和 ${c}$ 是朋友且 ${a}$ 和 ${c}$ 之间没有任何直接关系，那么 ${a,c}$ 就互为对方的潜在好友。这里的直接关系是指的不在给出的 ${m}$ 对朋友关系里，也不在给出的 ${k}$ 对仇敌关系里。也就是说，朋友的朋友就是潜在好友，中间可以隔很多个朋友，也算是潜在好友。 现在给你这些关系，请你计算每位用户有多少潜在好友。 ## 输入格式 第一行给出三个以空格分隔的整数 ${n,m,k}$，含义如题所示 接下来 $m$ 行每行给出两个正整数 $a_i,b_i$，表示 $a_i,b_i$ 两位用户是朋友关系 最后 $k$ 行每行给出两个正整数 $c_i,d_i$，表示 $c_i,d_i$两位用户是仇敌关系 $2 \le n \le 10^5$ $0 \le m, k \le 10^5$ $1 \le a_i,b_i,c_i,d_i \le n$ 输入保证两个用户之间的关系不会重复给出，也不会有两个用户之间既是朋友也是仇敌 ## 输出格式 在一行中输出 nn 个以空格分隔的整数，依次代表每位用户潜在的好友数量 ## 输入 ```in1 4 4 1 2 1 1 3 3 2 3 4 4 1 ``` ## 输出 ```out1 0 1 0 1 ``` ```in2 5 10 0 1 2 1 3 1 4 1 5 3 2 2 4 2 5 4 3 5 3 4 5 ``` ```out2 0 0 0 0 0 ``` ## 提示