CF2277C Edge Addeleting

[Frums - Credits](https://www.youtube.com/watch?v=EOTAWLaDa58) You are given a tree with $ n $ vertices, numbered from $ 1 $ to $ n $ . You need to perform $ m $ operations on this tree. The $ i $ -th operation consists of two steps: 1. an edge between vertex $ 1 $ and vertex $ v_i $ is added, which creates a cycle; 2. you choose one edge of this cycle (possibly the newly added one) and delete it, so the graph becomes a tree again. If there is already an edge between vertex $ 1 $ and vertex $ v_i $ , the new edge is still added, and the cycle consists of these two parallel edges. Find the maximum possible distance $ ^{\text{∗}} $ between vertices $ 1 $ and $ n $ after all $ m $ operations. $ ^{\text{∗}} $ The distance between two vertices in a tree is the number of edges on the unique simple path between them.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ m $ ( $ 2 \le n \le 5 \cdot 10^5 $ , $ 1 \le m \le 5 \cdot 10^5 $ ) — the number of vertices and the number of operations. Each of the next $ n - 1 $ lines contains two integers $ x $ and $ y $ ( $ 1 \le x, y \le n $ , $ x \ne y $ ) — an edge of the initial tree. It is guaranteed that the given edges form a tree. The next line contains $ m $ integers $ v_1, v_2, \ldots, v_m $ ( $ 2 \le v_i \le n $ ), describing the operations. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 5 \cdot 10^5 $ . It is guaranteed that the sum of $ m $ over all test cases does not exceed $ 5 \cdot 10^5 $ .

For each test case, output a single integer — the maximum possible distance between vertices $ 1 $ and $ n $ after all $ m $ operations.

In the first test case, the tree consists of a single edge $ (1, 2) $ , and it stays the same after every operation. Thus, the answer is $ 1 $ . In the second test case, the distance between vertices $ 1 $ and $ 3 $ is initially $ 2 $ , and neither operation can increase it. Thus, the answer is $ 2 $ . In the third test case, we can delete the newly added edge in the first operation. In the second operation, the edge $ (1, 5) $ is added, and we delete the edge $ (1, 2) $ . After that, the path from $ 1 $ to $ 7 $ is $ 1 \to 5 \to 4 \to 2 \to 3 \to 7 $ , so the distance is $ 5 $ . It can be shown that no larger distance is possible. Thus, the answer is $ 5 $ .