Longest Prime Path in a Tree

This problem involves a tree with N nodes and N-1 edges. Each edge connects two nodes and has a weight. Your task is to find the length of the longest simple path (in terms of the number of edges) such that every edge in the path has a weight that is a prime number.

Input Format:

• The first line consists of an integer N, representing the number of nodes in the tree.
• The next N-1 lines each contain three space-separated integers u, v and w, representing an edge between nodes u and v with weight w.

Output Format:

• Output a single integer representing the length of the longest path where all edge weights are prime numbers. If no such path exists, output 0.

Note: A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. In mathematical terms, a number x is prime if and only if \( x \gt 1 \) and \( \forall d \in \mathbb{N},\, (1 < d < x) \Rightarrow (d \nmid x) \).

inputFormat

The input is read from stdin and has the following format:

N
u1 v1 w1
u2 v2 w2
... 
u(N-1) v(N-1) w(N-1)

where N is the number of nodes, and each of the next N-1 lines contains three integers representing an edge of the tree.

outputFormat

Print the length of the longest path (number of edges) consisting solely of edges with prime weights to stdout.

## sample

5
1 2 3
2 3 5
3 4 7
4 5 4

3