#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

数据范围与提示