Given a tree of N nodes whose vertices are numbered from 1 to N. We need to remove two edges from tree to form three connected components. And we want to minimize the difference of maximum of xors and minimum of xors of the vertices of the connected components.

For eg. our graph is as follows:
N= 4
Edges E are as follows:
1 2
2 3
4 1
if we remove 2-3 and 1-2 then are connected components are:
2 (xor = 2)
3 (xor=3)
1-4 (xor=5)
and then for for this case difference of xors is max(2,3,5) - min(2,3,5) = 5 - 2 = 3 and we need to minimize this difference.

First line of input is T = number of test cases. Then for each test case we take input N = number of vertices, then following N-1 lines takes input for edges of the tree.

Constraints:
1<=T<=10
N<=3000

I came up with naive approach of trying to remove all possible combinations of edges and take minimum of xors difference. The time complexity of my approach was O(n^3) = O(n^2) for trying each combination and O(n) to find xor of vertices in connected components. But i got TLE. How can we optimize it?