Maximum Safety
Tag(s):

## Medium-Hard

Problem
Editorial
Analytics

Kevin wants to hide from Marv in the city. The city consists of N junctions connected with roads. There are $N-1$ roads, each of length 1. So the city is a tree. Root of this tree is junction 1.

For each of the next M days Kevin wants to hide in one of the junctions. Kevin knows that Marv is located in junction $a_i$ on the i-th day. Kevin also believes that junction v is safe only if v is in the subtree of vertex $b_i$. The safety of vertex v is equal to the distance between v and $a_i$. Help Kevin to find the maximum safety possible for each day.

Input format:

The first line of input will contain an integer T, denoting the number of test cases.
Each test case starts with 2 numbers N and M. Next $N-1$ lines contains 2 numbers $u_i$ and $v_i$ - junctions connected by a road. Next M lines contains 2 numbers $a_i'$ and $b_i'$. To find actual values of $a_i$ and $b_i$ Kevin does the following steps:

• let $d_{i-1}$ be the answer on $i-1$-th day.
• $a_i = ((a_i' - 1 + d_{i-1})\space mod \space N) + 1$
• $b_i = ((b_i' - 1 + d_{i-1})\space mod \space N) + 1$
• assume that $d_0=0$

Output format:

For every test case output M numbers - maximum safety for each day.

Constraints:

• $1 \le T \le 10$
• (20 points): $1 \le N \le 1000, 1 \le M \le 1000$
• (30 points): $1 \le N \le 10^5, 1 \le M \le 10^5$ , $a_i$ is not in the subtree of $b_i$.
• (50 points): $1 \le N \le 10^5, 1 \le M \le 10^5$.
SAMPLE INPUT
1
7 4
1 2
1 3
1 4
4 5
4 6
5 7
2 4
1 7
1 1
4 1

SAMPLE OUTPUT
4
2
0
2

Explanation

Actual values of $a_i$ and $b_i$:
Day 1 : $a_1 = 2 , b_1 = 4$
Day 2 : $a_2 = 5 , b_1 = 4$
Day 3 : $a_1 = 3 , b_1 = 3$
Day 4 : $a_1 = 4 , b_1 = 1$

Tree from the sample case:

On the first day junction 7 has the maximum safety and its distance from junction 2 is 4. On the second day junction 6 has the maximum safety and its distance from junction 5 is 2. Note that distance to junction 2 is 3 but junction 2 is not safe as it is not in the subtree of juntion 4.

Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

September Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Graphs