Hide

Problem P
A Tree and Two Edges

Given a connected simple graph (with at most one edge between any pair of nodes) with n nodes and n+1 edges (that’s a tree with two extra edges), answer a list of queries: for two distinct nodes, how many simple paths are there between them? A simple path is a path that does not repeat nodes.

Input

The first line of input contains two integers n (4n5×104) and q (1q5×104), where n is the number of nodes and q is the number of queries. The nodes are numbered from 1 to n.

Each of the next n+1 lines contains two integers a and b (1a<bn) indicating that there is an edge in the graph between nodes a and b. All edges are distinct.

Each of the next q lines contains two integers u and v (1u<vn). This is a query for the number of simple paths between nodes u and v.

Output

Output q lines. On each line output a single integer, which is the number of simple paths between the query nodes. Output the answers to the queries in the order they appear in the input.

Sample Input 1 Sample Output 1
4 6
1 2
1 3
1 4
2 3
2 4
1 2
1 3
1 4
2 3
2 4
3 4
3
3
3
3
3
4
Sample Input 2 Sample Output 2
6 4
1 2
1 3
1 6
2 3
3 4
3 5
4 5
1 2
1 3
1 4
1 6
2
2
4
1
Hide

Please log in to submit a solution to this problem

Log in