問題文
AtCoder 城市有 编号至 1 到 N 有 N 个城镇,分别是 N-1 一本书可以在两个方向上通过的距离 它们由 1 道路连接。 您可以通过多条道路从任何城镇前往任何其他城镇。
Takahashi先生在AtCoder City。 Q 有人,i 高桥君是镇 s_i 卡拉町 我想去 t_i 。
AtCoder市的几个城镇都有章鱼烧店。高桥和大家,2 每秒距离 1 我走路的速度与走路时的速度相同,但是在有章鱼烧店的小镇吃完章鱼烧后,我的步行速度变慢了。 1 每秒距离 1 这是您前进的速度。 而且,高桥和他的朋友们都是清淡饮食者,所以他们吃章鱼烧的次数不会超过一次。当然,路过有章鱼烧店的小镇,不吃章鱼烧也是可以的。 另外,不吃章鱼烧就不要进城。 您可能会到达 t_i 。
考虑到AtCoder城市和城镇的连接关系, Q 高桥君,你为每个人都表现得最好的小镇。 求前往 s_i 卡拉町 我想去 t_i所需的最短时间。 由于高桥和他的朋友都是章鱼烧专业人士,所以我们可以忽略吃章鱼烧所需的时间。
入力
输入是按以下格式从标准输入给出的。
N Q
A_1 B_1
.
.
.
A_{N-1} B_{N-1}
S
s_1 t_1
.
.
.
s_Q t_Q
- 1 行包含一个整数 N(1 ≦ N ≦ 100000) 和 Q(1 ≦ Q ≦ 100000) 作为空格分隔符给出。
- 继续 N-1 行包含 代表第 i 条路径信息的整数 A_i, B_i(1 ≦ A_i ≦ N, 1 ≦ B_i ≦ N, A_i ≠ B_i) 作为空格分隔符给出。这就是小镇 A_i 和镇 表示有一条路径连接 B_i 。
- 以下行包含 仅由0 和 1 组成的长度 给出了字符串 N 。这个 i 第一个字母是 0 能时镇 i 没有章鱼烧餐厅。1 能时镇 i 表示有一家章鱼烧餐厅。
- 继续 Q 行包含 代表第i 一个整数,表示人的运动起点和终点,Takahashi。 s_i,t_i(1 ≦ s_i ≦ N, 1 ≦ t_i ≦ N) 。
出力
输出是 由 Q 行组成。
i 行中, 一个整数,表示第i 让我们计算一下这个人的高桥君达到最佳移动所需的最短时间。 1 行输出。
不要忘记输出末尾的换行符。
入力例1
7 4 1 2 2 3 2 4 4 5 5 6 6 7 0010000 1 5 1 7 6 1 3 3
出力例1
6 9 8 0
在第一个查询中,镇 最好按顺序访问 1,2,4,5 。 在第 2 次查询中,镇 1,2,3,2,4,5,6,7 和沿途的城镇。 最好去 3 的章鱼烧店。
入力例2
5 2 3 2 2 4 1 4 2 5 00000 1 5 2 3
出力例2
6 2
入力例3
12 10 1 2 2 3 2 4 10 12 1 5 3 11 5 6 9 10 5 7 3 9 8 7 000100100010 1 2 1 4 8 3 6 12 12 8 8 12 6 8 8 6 1 12 5 12
出力例3
2 4 6 11 14 9 5 4 9 9