Chor Police

Problem Statement

Chor Police Problem Description The police is standing on the root of the tree, vertex 1. They are trying to catch a thief who is on the vertex x. The thief moves first and then the police. They move in turns and on every turn, they can either stand on the current vertex or move to a neighboring vertex. Police and thief know each other's position after every move. Police will always catch the thief. Police are trying to minimize the time and the thief is trying to maximize it. Find how many moves it will take to catch the thief Input Format First line contains n, the number of vertices. Second line contains x, the position of thief. Third line contains n-1 integer. Fourth line contains integer 2. Next n-1 lines contains two integer numbers a and b Constraints 2 <= n <= 10 4 2 <= x <= n 1 <= a,b <= n Output Format Return the number of moves to catch the thief. Examples Example 1: Input: 4 3 3 2 1 2 2 3 2 4 Output: 4 Explanation: Based on the edges, Thief will stay away