Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4008
Yet Another Tree Query Problem

Time Limit: 3 Seconds      Memory Limit: 65536 KB

Given a tree with \(n\) vertices, which are numbered by integers from 1 to \(n\), there are \(q\) queries.

Each query can be described with two integers \(l\) and \(r\). A vertex \(v\) is good, if and only if \(l \le v \le r\); An edge \((u, v)\) is good, if and only if both \(u\) and \(v\) are good. Please print the number of connected components consist of all the good vertices and the good edges.

Input

There are multiple test cases. The first line of the input is an integer \(T\) (about 5), indicating the number of test cases. For each test case:

The first line contains two integers \(n\) and \(q\) (\(1 \le n, q \le 2 \times 10^5\)), indicating the number of vertices and the number of queries.

The following \((n-1)\) lines each contains two integers \(u\) and \(v\) (\(1 \le u, v \le n\)), indicating an edge connecting vertex \(u\) and \(v\) in the tree.

The following \(q\) lines each contains two integers \(l\) and \(r\) (\(1 \le l \le r \le n\)), indicating a query.

It's guaranteed that the given graph is a tree.

Output

For each query output one line containing one integer, indicating the answer.

Sample Input

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

Sample Output

2
1
1
2
1
1
2
1

Hint

For the six queries in case 1, the connected components are listed as follows:

[1], [2]
[2, 3]
[3, 4]
[1], [2, 3]
[2, 3, 4]
[1, 2, 3, 4]

For the two queries in case 2, the connected components are as follows:

[1], [2]
[2, 3]


Author: WANG, Yuhan
Source: ZOJ Monthly, March 2018
Submit    Status