#2522. 树上距离

树上距离

Description

nn 栋房屋,由一些双向道路连接起来。每两栋房屋之间都有一条独特的简单道路(“简单”意味着不可以通过两条道路去一个地方)。人们每天总是喜欢这样问:“我从A房屋到B房屋需要走多远?”

Format

Input

第1行是单个整数TT T10(T ≤10),表示测试用例的数量。每个测试用例的第1行都包含n2n40000n (2≤n ≤40000)m1m200m (1≤m ≤200),表示房屋数量和查询数量。下面的n1n -1行,每行都包含三个数字iijjkk,表示有一条道路连接房屋i和房屋j,长度为k0<k40000k(0<k≤40000),房屋被标记为1n1~n 。接下来的mm 行,每行都包含两个不同的整数iijj ,求房屋ii 和房屋jj 之间的距离。

Output

对每个测试用例,都输出mm 行查询答案,在每个测试用例后都输出一个空行。

Samples

2
3 2
1 2 10
3 1 15
1 2
2 3
2 2
1 2 100
1 2
2 1
10
25

100
100

来源

HDU2586