Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Meena Raju and Two Trees

By ovis96 · Limits 2s, 512 MB

Meena's father gifted Meena and Raju two trees. Since they may quarrel, these two trees are exactly the same including label. Meena defines a node of a tree deaf node, if it has atmost one adjacent node.

Since these two trees are exactly the same, Meena used the following algorithm to connect these two trees and make a graph from them.

Let nn be the number of nodes in the tree. For every similar deaf node of the two trees, merge them into one node with the same label. By this way it creates one connected graph. But this graph may have some label of nodes twice. To solve this issue Raju suggested that, labels of Meena's tree remain exactly the same but for Raju's tree, the label of every node will be changed into previous label added by nn. Note that, label of the deaf nodes will not change!

Now Meena and Raju have a graph with unique labels! Meena wants to find qq queries of the shortest path between node aia_i to bib_i (1iq1 \leq i \leq q) in this graph.

For example, let's consider the tree of Meena and Raju as following:

Then after merging these two trees, they will convert into the second graph.

Input

First line will contain an integer T, ( 1T101 \leq T \leq 10, the number of test cases).

For every test case, there will be two integers, n qn \ q (1n1051 \leq n \leq 10^5, the number of nodes in Meena and Raju's initial tree, 1q1051 \leq q \leq 10^5, the number of queries).

Following n1n-1 lines will contain two integers u vu\ v (that means there is an edge between uu and vv in the tree).

The following qq lines each will contain ai bia_i\ b_i for 1iq1 \leq i \leq q and 1ai,bi2n1 \leq a_i, b_i \leq 2n, Meena's query nodes.

You can assume that all aia_i and bib_i are valid.

Output

For each query, print a single line denoting the length of the shortest path between aia_i and bib_i.

Sample

InputOutput
2
5 2
1 2
1 3
3 4
3 5
3 8
2 5
3 2
1 2
1 3
1 4
2 4
2
3
2
1

    Discussion

    Statistics


    33% Solution Ratio

    shefinEarliest, 8M ago

    shefinFastest, 0.9s

    shefinLightest, 27 MB

    shefinShortest, 3706B

    Submit

    Login to submit

    Editorial

    This is an easy problem. There are two cases we need to solve, and they are, The two nodes belong...

    Related Contests

    Toph uses cookies. By continuing you agree to our Cookie Policy.