Finding the Optimal Tree Partition

You are given one or more trees. For each tree, you must remove a single edge such that the difference between the number of nodes in the two resulting trees is minimized. In other words, if one tree has s nodes and the other has N-s nodes, you want to minimize \(|N-2s|\). In the event of a tie (i.e. two candidate edges yield the same difference), choose the edge where the parent vertex (i.e. the vertex closer to the root) is at a shallower depth.

Each tree is rooted at node 1. All trees are undirected and connected. It is guaranteed that the input data forms a valid tree. The removed edge should be output in the order \( (u, v) \) where u is the parent of v (i.e. the node with smaller depth).

Note: Use depth-first search to compute subtree sizes and maintain the best candidate edge by checking \(|N-2\times{subtreeSize}|\). Use LaTeX formatting for all mathematical formulas in your explanation.

inputFormat

The first line contains an integer \(T\) representing the number of trees.

For each tree:

• The first line contains an integer \(N\), the number of nodes.
• The next \(N-1\) lines each contain two integers \(u\) and \(v\), indicating an edge between nodes \(u\) and \(v\).

Assume that node 1 is the root of the tree.

outputFormat

For each tree, output a single line with two integers \(u\) and \(v\) (separated by a space) representing the edge that should be removed. The edge must be output in the order \( (u, v) \) where \(u\) is the parent (closer to the root) and \(v\) is the child.

## sample

2
3
1 2
1 3
4
1 2
1 3
3 4

1 2
1 3

</p>