BZPRO

#4298. [ONTAK2015]Bajtocja

内存限制：256 MiB 时间限制：10 Sec
提交 提交记录 讨论

题目描述

给定d张无向图，每张图都有n个点。一开始，在任何一张图中都没有任何边。接下来有m次操作，每次操作会给出a,b,k，意为在第k张图中的点a和点b之间添加一条无向边。你需要在每次操作之后输出有序数对(a,b)的个数，使得1<=a,b<=n，且a点和b点在d张图中都连通。

输入格式

第一行包含三个正整数d,n,m(1<=d<=200，1<=n<=5000，1<=m<=1000000)，依次表示图的个数，点的个数和操作的个数。
接下来m行，每行包含三个正整数a,b,k(1<=a,b<=n，1<=k<=d)，依次描述每一个操作。

输出格式

输出m行m个正整数，依次表示每次操作之后满足条件的有序数对(a,b)的个数。

样例

样例输入


			
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

样例输出


			
4

4

6

6

6

6

6

8

8

16

数据范围与提示

BZPRO Powered by Remmina.
Github Repository