Welcome to ZOJ
 Problem Sets 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