시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 | 512 MB | 6 | 0 | 0 | 0.000% |
A cat and a mouse play a game inside an undirected tree graph with N vertices numbered from 1 to N. The cat is initially located in vertex 1, and the mouse in vertex M. Each edge of the tree has a unique quantity of cheese (from 1 to N-1). The cat and the mouse move alternately, starting with the mouse. At its turn, the mouse moves from its current vertex to a neighboring vertex, using the edge with the largest quantity of cheese. If the cat is located in the chosen vertex, then the mouse will move to the second best neighboring vertex (i.e. the vertex connected to the current vertex with an edge having the 2nd largest quantity of cheese). If there is no second vertex to move to, then the game ends and the cat wins. At its turn, the cat can move to any neighboring vertex or stay in its current vertex.
You control the cat and you want to win the game as soon as possible. Find the minimum possible number of moves the mouse will make before the cat wins the game.
The first line of the input file contains the number of test cases T. Then the T test cases follow. The 1st line of each test case contains the number N and M. The next N-1 lines contain two numbers u and v each, denoting an edge between the vertices u and v. The k th of these edges (1 ≤ k ≤ N-1) has a quantity of cheese equal to k.
Constraints
For each test case, in the order given in the input, print one line containing the minimum number of moves the mouse will make before the cat wins the game (assuming the cat plays optimally). Print -1 if the cat cannot win the game.
3 10 10 6 7 6 5 5 4 4 1 1 2 1 3 7 8 8 9 9 10 10 6 6 7 6 5 5 4 4 1 1 2 1 3 7 8 8 9 9 10 13 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 5 4 4 3 3 1 1 2
6 4 4
ICPC > Regionals > Europe > Southeastern European Regional Contest > SEERC 2017 H번