Multiple Graph Connectivity

Given d undirected graphs each with n vertices, initially with no edges, perform m operations. Each operation is described by three integers a, b, k, meaning that an undirected edge is added between vertices a and b in the k-th graph. After each operation, output the number of ordered pairs \((a, b)\) (where a pair is counted even if \(a = b\)) with \(1 \leq a, b \leq n\) such that vertices \(a\) and \(b\) are connected in every one of the d graphs. The connectivity in each graph is defined in the usual sense: two vertices are connected if there is a path between them in that graph.

The answer for each operation is calculated by first grouping the vertices by their connectivity signatures across all graphs. Here, the connectivity signature of a vertex is a tuple \((r_1, r_2, \ldots, r_d)\), where \(r_i\) is the representative (or root) of that vertex in the union-find structure for the \(i\)-th graph. For each group of vertices of size \(s\), the contribution to the answer is \(s^2\) (since ordered pairs are counted).

Note: All formulas are represented in LaTeX format.

inputFormat

The input begins with a line containing three integers d, n, and m:

• d is the number of graphs.
• n is the number of vertices in each graph.
• m is the number of operations.

Each of the following m lines contains three integers a, b, and k, representing an operation to add an undirected edge between vertices a and b in the k-th graph. Vertices are numbered from 1 to n and graphs are numbered from 1 to d.

outputFormat

After each operation, output a single integer on a new line representing the number of ordered pairs \((a, b)\) (with \(1 \leq a, b \leq n\)) such that vertices \(a\) and \(b\) are connected in every one of the d graphs.

sample

2 3 3
1 2 1
2 3 2
1 3 1

3
3
5