B"Master Andrey loves trees ^{ dagger} very much, so he has a tree consisting of n vertices. But it's not that simple. Master Timofey decided to steal one vertex from the tree. If Timofey stole vertex v from the tree, then vertex v and all edges with one end at vertex v are removed from the tree, while the numbers of other vertices remain unchanged. To prevent Andrey from getting upset, Timofey decided to make the resulting graph a tree again. To do this, he can add edges between any vertices a and b , but when adding such an edge, he must pay |a - b| coins to the Master's Assistance Center. Note that the resulting tree does not contain vertex v . Timofey has not yet decided which vertex v he will remove from the tree, so he wants to know for each vertex 1 <= q v <= q n , the minimum number of coins needed to be spent to make the graph a tree again after removing vertex v , as well as which edges need to be added. ^{ dagger} A tree is an undirected connected graph without cycles. Each test consists of multiple test cases. The first line contains a single integer t ( 1 <= t <= 10^4 ) -- the number of test cases. The description of the test cases follows. The first line of each test case contains a single integer n ( 5 <= n <= 2 cdot10^5 ) -- the number of vertices in Andrey's tree. The next n - 1 lines contain a description of the tree's edges. The i -th of these lines contains two integers u_i and v_i ( 1 <= u_i, v_i <= n ) -- the numbers of vertices connected by the i -th edge. It is guaranteed that the given edges form a tree. It is guaranteed that the sum of n over all test cases does not exceed 2 cdot10^5 . For each test case, output the answer in the following format: For each vertex v (in the order from 1 to n ), in the first line output two integers w and m -- the minimum number o"...