题目描述

中二少年$\red{cenbo}$幻想自己统治着$\red{Euphoric Field}$。由此他开始了$\red{Endless Fantasy}$。

$\red{Euphoric Field}$有$\red{n}$座城市，$\red{m}$个民族。这些城市之间由$\red{n-1}$条道路连接形成了以城市$\red{1}$为根的有根树。

每个城市都是某一民族的聚居地，$\red{cenbo}$知道第$\red{i}$个城市的民族是$\red{A_i，}$人数是$\red{B_i}$。为了维护稳定，$\red{cenbo}$需要知道某个区域内人数最多的民族。

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

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

输入格式

输入文件$\red{endless.in}$共有$\red{2\times n}$行。

第一行有两个整数$\red{n, m}$。

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

接下来$\red{n}$行，第$\red{i}$行有两个整数$\red{A_i, B_i}$。

输出格式

输出文件$\red{endless.out}$共有$\red{n}$行。

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

样例

输入样例

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

提示

数据范围

$\red{30\%}$的数据，$\red{n<=1000}$；

$\red{60\%}$的数据，$\red{n<=40000}$；

$\red{100\%}$的数据，$\red{n<=400000，}$$\red{m<=n，}$$\red{1<=A_i<=m，}$$\red{0<=B_i<=1000}$。

输入文件较大请使用读入优化。