Balanced Parenthesis Paths in Directed Graph

You are given a directed graph with n vertices and 2m edges. Each edge is labeled with a parenthesis symbol. There are k different types of parentheses (indexed from 1 to k), so there are 2k possible labels: a left parenthesis and a right parenthesis for each type. The vertices are numbered from 1 to n.

It is guaranteed that the edges appear in pairs. More specifically, if there is a left parenthesis edge of type (w) from vertex u to vertex v, then there is a corresponding right parenthesis edge of type (w) from vertex v to vertex u. Similarly, every right parenthesis edge has a corresponding reverse edge marked with the same type left parenthesis.

Your task is to count the number of vertex pairs ((x,y)) with (1 \le x < y \le n) such that there exists a (non‐simple) walk from x to y in the graph for which the concatenation of the labels on the edges (in the order they are traversed) forms a valid parenthesis sequence. A valid parenthesis sequence is defined in the usual way: the empty string is valid, and if A is valid then ((A)) is valid, and if A and B are valid then their concatenation AB is valid. (All formulas are given in LaTeX format.)

inputFormat

The first line contains three integers n, m and k, where n is the number of vertices, m is half the total number of edges, and k is the number of different parenthesis types.

Then follow m lines, each containing three integers u, v, w, describing a directed edge from u to v with a left parenthesis of type w.

Then follow another m lines, each containing three integers u, v, w, describing a directed edge from u to v with a right parenthesis of type w.

You may assume that \(1 \leq u,v \leq n\) and \(1 \leq w \leq k\). It is guaranteed that for every left parenthesis edge \((u,v)\) with type w, there is a corresponding right parenthesis edge \((v,u)\) with type w, and vice versa.

outputFormat

Output a single integer: the number of pairs \((x, y)\) (with \(1 \le x < y \le n\)) for which there exists a walk from x to y whose concatenated edge labels form a valid parenthesis sequence.

sample

2 1 1
1 2 1
2 1 1

0