Path Killer
题号:NC216180
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

MainKing has a rooted tree with nodes, and paths on it. And the root of this tree is .

The endpoints of the i-th path are a_i,b_i. All of these paths satisfy a special condition: a_i is on the path from b_i to the root. 

Now MianKing wants to delete all of these paths. He will do the following operation until all of the paths are deleted: choose an integer from randomly and delete all of the paths where is on.

MianKing wants you to calculate the expected number of operations he need to do.

It's guaranteed that the answer will converge to some rational number.

If the answer is irreducible fraction , you need to output an integer in which satisfies . It's guaranteed that

输入描述:

The first line has two integers .

The second line has integers, the i-th integer denotes the father node of node

Then there are lines, the i-th line has two integers a_i,b_i.



Let fa_i denote the father node of node . Then for

. It's guaranteed that a_i is on the path from b_i to the root.

输出描述:

Output the answer.
示例1

输入

复制
3 3
1 1
1 2
3 3
1 1

输出

复制
499122181