ADAPHONE - Ada and Contact

You might already know that Ada the Ladybug has some friends who live on a plum tree. Those friends are numbered from 1 to N (where N is the number of her friends). Ada freely travels on the tree from one friend to another. As she passes a friend (with ID i), he/she always tells her "Hey Ada! If you meet i+1 or i-1, please give him my phone number.". Also note that as long as someone obtains phone number of someone else, he distributes it to all friends whose number he/she has.

Ada will undertake many walks on the tree (from one friend to another) and she ask you (for each walk), how many independent sets of friends she will make during her walk. The two sets are independent if nobody from one set has a number of someone else in the other set (and vice versa).

NOTE: All walks are independent of each other (so no phone-distribution remains from previous walks).

Input

The first line will contain two integers 1 ≤ N, Q ≤ 2*105, the number of Ada's friends and the number of walks

The next N-1 lines will contain two integers 1 ≤ a, b ≤ N, meaning that there is a branch (edge) between ath and bth friend.

The next Q lines will contain two integers 1 ≤ a, b ≤ N, meaning that Ada will take walk between ath and bth friend.

Output

For each query, print the number of independent sets Ada will create by her walk (counting only friends on her path).

Example Input

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

Example Output

3
1
2
2
2
1

Example Input 2

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

Example Output 2

2
2
2
3
2

Example Input 3

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

Example Output 2

2
1
4
1
3
4
2
3
3
1

Added by:Morass
Date:2017-09-21
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2023-01-25 20:42:03
Why i'm getting TLE ?
<snip>
My complexity is O(N ^ (5/3) )
[Simes]: use the forum for this.

Last edit: 2023-01-25 22:37:15
2018-06-14 06:41:53
getting WA in Judge 15...any corner case suggestions???
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.