抓人游戏
题号：NC238015
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

牛牛和牛妹正在玩一款游戏，牛牛有 m 只极其聪明的虫子，而牛妹有一个笨笨的机器人。

游戏在一颗有 n 个点的无向无根树上进行。

初始时第 只虫子分别处在编号为 的结点上，而机器人处在编号为 x 的结点上（每个结点可以同时容纳无数个单位，所以初始位置可能会重叠）。

游戏开始，机器人会按照 的顺序来抓取每一只虫子，而每只虫子都是极度聪明的，他们遵循的法则是：“使自己尽可能晚的被机器人抓住，在此前提下使下一只被抓的虫子也尽可能晚的被抓住”。规定：每一秒钟，虫子和机器人都可以通过一条树上边从一个结点到另一个结点上（如果在某一条边上行进时机器人和它当前所要抓取的虫子处于相向而行的状态，那么就认为机器人在这条边的中点处抓住了目标（花费 0.5 秒）），当然，机器人和虫子也可以选择停留在当前结点而不行动，我们认为机器人抓住虫子这个动作是不需要花费时间的，案例中有所体现。

为了使游戏更加的有趣，牛妹和牛牛分别使用了魔法禁锢了虫子和机器人，就是说第 只虫子分别需要在第 时刻才可以开始行动，而机器人则要在第 y 时刻才可以开始行动。（即便被禁锢，机器人只要和当前想要抓的虫子相遇了，机器人还是可以抓住虫子的）

现在给你上述的这些信息，牛牛和牛妹想请你帮忙计算一下每只虫子被抓住的时刻分别是多少。

输入描述:

第一行输入两个整数分别代表 n,m 。
第二行输入  个用空格分割的整数分别代表  和 x 。
第三行输入  个用空格分割的整数分别代表  和 y 。
接下来输入 n-1 行，每行两个整数  代表编号为 u 和编号为 v 的结点之间存在一条边。
保证：
输入数据是一棵树
 

输出描述:

输出共一行 m 个整数分别代表第  只虫子被抓住的时刻（游戏开始时是第 0 时刻）。
示例1

输入

复制 
9 6
3 3 4 6 6 2 3
9 0 0 2 3 100 0
1 2
2 3
3 4
2 6
6 5
6 7
1 8
8 9

输出

复制 
0 0 1 5 10 13

说明

一种可能的最优解是：
机器人在编号为 3 的结点处先后抓住了虫子 1 和 虫子 2。（花费了 0 步）
机器人在编号为 4 的结点处抓住了虫子 3。（花费了 1 步）
机器人在编号为 5 的结点处抓住了虫子 4。（花费了 4 步）
机器人在编号为 9 的结点处抓住了虫子 5。（花费了 5 步）
机器人在编号为 2 的结点处抓住了虫子 6。（花费了 3 步）