[ONTAK2015] Bajtocja
题目描述
给定 $d$ 张无向图,每张图都有 $n$ 个点。一开始,在任何一张图中都没有任何边。接下来有 $m$ 次操作,每次操作会给出 $a, b, k$,意为在第 $k$ 张图中的点 $a$ 和点 $b$ 之间添加一条无向边。你需要在每次操作之后输出有序数对 $(a, b)$ 的个数,使得 $1 \leq a, b \leq n$,且 $a$ 点和 $b$ 点在 $d$ 张图中都连通。
输入输出格式
输入格式
第一行,三个整数 $d, n, m$;
接下来 $m$ 行,每行三个整数 $a, b, k$。
输出格式
$m$ 行,每行一个整数,表示所求的值。
输入输出样例
输入样例 #1
3 4 10
1 2 1
2 1 2
1 2 3
3 4 1
1 3 2
2 3 3
2 4 2
3 4 3
3 4 2
1 3 1
输出样例 #1
4
4
6
6
6
6
6
8
8
16
说明
对于 $100\%$ 的数据,$1 \leq d \leq 200$,$1 \leq n \leq5 \times 10^3$,$1\leq m \leq 10^6$,$1 \leq a, b \leq n$,$1 \leq k \leq d$。