题目描述

《两点最短距离》

给出 n 个点的一棵树，多次询问两点之间的最短距离。

输入格式

第一行为3个整数 n, m, s。n 表示点数，m 表示询问次数，s表示根节点编号； 下来 n-1 行，每行三个整数 x,y,k，表示点 x 和点 y 之间存在一条边长度为 k； 再接下来 m 行，每行两个整数 x,y，表示询问点 x 到点 y 的最短距离。 树中结点编号从 1 到 n。

输出格式

共 m 行，对于每次询问，输出一行询问结果。

样例

输入样例 1

6 2 2
1 2 1
1 3 1
2 4 1
2 5 1
3 6 1
2 6
5 6

输出样例 1

3
4

输入样例 2

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

输出样例 2

9
7
1
0
3

输入样例 3

6 3 1
1 2 2
2 3 2
2 4 3
4 5 3
5 6 3
2 6
6 3
3 4

输出样例 3

9
11
5

输入样例 4

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

输出样例 4

4
4
4
4
4
4

输入样例 5

15 7 1
1 2 3
1 3 3
2 4 3
2 5 3
3 6 3
3 7 3
4 8 3
4 9 3
5 10 3
5 11 3
6 12 3
6 13 3
7 14 3
7 15 3
8 15
9 10
4 14
6 7
2 3
11 13
12 15

输出样例 5

18
12
15
6
6
18
12

输入样例 6

12 6 3
3 1 5
3 2 5
3 4 5
4 5 5
4 6 5
5 7 5
5 8 5
6 9 5
6 10 5
7 11 5
8 12 5
1 12
2 11
5 9
7 10
3 8
6 12

输出样例 6

25
25
15
20
15
20

输入样例 7

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

输出样例 7

24
12
28
16
8