[ONTAK2015]Bajtocja

时间限制:10s      空间限制:256MB

题目描述

给定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

提示

没有写明提示


题目来源

By Claris