You are given a tree of $n$ vertices
Let $f(u, v)$ be the shortest distance between $u$ and $v$. You are given $q$ queries, each of the form $(u, v)$, counting the number of vertices $x$ that $$f(u, x) = f(v, x)$$
### Input
- The first line contain 2 integers $n, q$.
- The next $n - 1$ lines, each line contains 2 integers $u, v$, there is an edge between $u$ and $v$.
- The next $q$ lines, each line contains 2 integers $u, v$, an query.
### Output
- Print $q$ integers, the answers to $q$ queries.
### Constraints
- $1 \le n, q \le 10^5$.
- $1 \le u, v \le n$.
### Example
Input:
```
7 3
1 2
1 3
2 4
2 5
3 6
3 7
1 4
5 6
3 7
```
Output:
```
2
1
0
```
