Longest Same Value Path

You are given a tree with n nodes, where each node has an associated integer value. The tree is described by n - 1 edges connecting the nodes. A path in the tree is a sequence of nodes such that each consecutive pair of nodes is connected by an edge. The task is to find the length (i.e. the number of edges) of the longest path in which every adjacent pair of nodes has the same value.

Formally, let a path be represented as a sequence of nodes v₁, v₂, ..., v_k. The path is considered valid if for each i (1 ≤ i < k), the condition

holds, where vi represents the value of the node. If no valid edge exists, output 0.

inputFormat

The input is read from stdin. The format is as follows:

1. The first line contains a single integer n (the number of nodes in the tree).
2. The next n - 1 lines each contain two space-separated integers u and v, representing an edge between nodes u and v.
3. The last line contains n space-separated integers representing the value of each node from node 1 to node n.

outputFormat

Output a single integer to stdout — the length (number of edges) of the longest path where all connected nodes share the same value.

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

2