题目描述

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