Bob has a tree with nodes, numbered from
to
. On the tree, there are
simple paths, numbered from
to
. The
-th simple path is from the node
to the node
. Bob wants to find out the longest common path between any two given paths. The longest common path is defined as the number of common edges between two paths.
Your task is to help Bob find out the length of the longest common path between any two given paths.
Input Specification:
The first line of input contains two integers and
(
), the number of nodes and the number of given paths.
The second line contains integers,
(
), indicating the parent of each node.
Each of the following lines contains two integers,
and
, (
and
), the two endpoints of the
-th given path.
Output Specification:
Output one integer, the length of the longest commont path.
Constraints
Subtask | Points | Additional constraints |
---|---|---|
No additional constraints. |
Sample Input 1:
4 2
1 2 2
1 3
1 4
Sample Output 1:
1
Sample Input 2:
7 3
1 2 2 4 5 5
1 3
3 7
6 1
Sample Output 2:
2
Comments