Page Contents

*Tag Game in a Tree Solution*

You are given a two-dimensional list of integers edges representing a tree, where each element is of the form [x, y] meaning there’s an undirected edge between x and y. You are also given integers u and v.

You are currently at node u, and your opponent is at node v. In the first round, you move, then in the next round your opponent moves, and then you move, and so on. Your opponent can choose to not make a move in a round. Return the minimum number of rounds it takes for you to catch your opponent, given that you both play optimally.

Constraints

n ≤ 100,000 where n is the length of edges

Example 1

Input

edges = [

[0, 1],

[1, 2]

]

u = 0

v = 2

Output

3

Explanation

First, you move from node 0 to 1. Then your opponent stays in the current node. And then you move to node 2.