Company: curefir_14oct
Difficulty: medium
Special nodes path You are given a tree with N nodes, numbered 1 to N . A tree is a connected undirected graph with exactly N - 1 edges, so every pair of nodes is already joined by exactly one simple path. K of the nodes are marked as special . You must perform the following operation exactly once : pick two different special nodes and add an undirected edge between them. The added edge is allowed to duplicate an edge that already exists. After the operation, report the distance between node 1 and node N , where the distance is the number of edges on a shortest path between them. Choose the two special nodes so that this distance is as small as possible. Input Format The first line contains a single integer T — the number of test cases. Each test case is given as five lines: The first line contains an integer N — the number of nodes in the tree. The second line contains an integer K — the number of special nodes. The third line contains K space-separated integers — the array special_no