Longest Colorful Path

You are given a directed graph with \(N\) nodes and \(M\) edges. Each node is labeled from 1 to \(N\) and each directed edge has a color \(c\) (\(1 \le c \le C\)). A path is considered colorful if no two consecutive edges share the same color. Your task is to determine the length of the longest colorful path.

Note: If the graph contains a cycle (i.e. there is no valid topological order), then a colorful path cannot be properly defined and you should output 0.

Input Constraints:

• \(1 \le N \le \text{some upper bound}\)
• \(0 \le M \le \text{some upper bound}\)
• \(1 \le C \le \text{some upper bound}\)
• Edges are given as triples of integers \((u, v, c)\), meaning there is a directed edge from node \(u\) to node \(v\) of color \(c\).

inputFormat

The input is given on the standard input. The first line contains three integers \(N\), \(M\), and \(C\) separated by spaces. Each of the following \(M\) lines contains three integers \(u, v, c\), describing a directed edge from node \(u\) to node \(v\) with color \(c\).

outputFormat

Output a single integer on the standard output representing the length of the longest colorful path. If the graph contains a cycle, output 0.

5 6 3
1 2 1
2 3 2
3 4 1
4 5 2
2 4 3
1 3 3

4