Description

有n座城市，m个民族。

这些城市之间由n-1条道路连接形成了以城市1为根的有根树。

每个城市都是某一民族的聚居地，Master知道第i个城市的民族是A_i，人数是B_i。

为了维护稳定，Master需要知道某个区域内人数最多的民族。

他向你提出n个询问，其中第i个询问是：求以i为根的子树内，人数最多的民族有是哪个，这个民族有多少人。

如果子树内人数最多的民族有多个，输出其中编号最小的民族。

Format

Input

共有2*n行。 第一行有两个整数n, m。

接下来n-1行，每行有两个整数u, v，表示一条连接u和v的道路。

接下来n行，第i行有两个整数A_i, B_i。 n<=400000，m<=n，1<=A_i<=m，0<=B_i<=1000。

Output

共有n行。

第i行两个整数x, y，分别表示以i为根的子树中人数最多的民族和它的人数。

Samples

8 6
1 2
1 3
2 4
4 5
3 6
5 7
1 8
2 8
2 5
1 1
3 1
6 7
5 6
1 10
4 6

2 13
1 10
5 6
1 10
1 10
5 6
1 10
4 6