Problem Statement

You are given a tree containing N nodes and K special nodes. You are allowed to perform exactly one operation on this tree: you can add one new edge between any two of the special nodes. After performing this operation, you must determine the minimum possible distance between node 1 and node N . The goal is to choose the two special nodes to connect such that the distance between node 1 and node N becomes as small as possible after adding that single edge. Parameters N : integer representing the total number of nodes in the tree. K : integer representing the number of special nodes. special_nodes : array of integers containing the indices of the special nodes. node_from : array of integers of size N − 1 representing the starting node of each edge. node_to : array of integers of size N − 1 representing the ending node of each edge. Input Format The first line contains an integer T , representing the number of test cases. For each test case: The first line contains an integer