There is a $$$n$$$-node tree with a special node $$$m$$$, Alice and Bob play a game on this tree, in which in each operation they must select an edge on the part of the tree where it exists, delete the edge and split the tree into two parts, keeping the part with the special node $$$m$$$ and deleting the other part. When there is only one node left in the tree, it is not possible to delete the edge, and the operator loses the game.
In each game, Alice starts, and the two players take turns, knowing that they will do the optimal operation in each round, so who wins the game if the special nodes $$$m$$$ are numbered from $$$1$$$ to $$$n$$$, respectively?
In the first line, an integer $$$t(1\le t \le 10^4)$$$, representing the number of data sets.
For each group of data:
The first line, one integer $$$n(1\le n \le 3·10^5)$$$, represents the number of nodes in the tree.
For the next $$$n-1$$$ rows, two integers $$$u,v(1\le u,v \le n)$$$ per row, representing one edge of the tree, ensuring that the input data is a tree.
It is guaranteed that the sum of $$$n$$$ within the same test point does not exceed $$$3·10^5$$$.
For each set of data, output a line of string $$$ans$$$ of length $$$n$$$, with the $$$i$$$ th character representing who wins the game if the special node $$$m$$$ is $$$i$$$. If Alice wins, $$$ans[i]$$$ is the character 'A'; otherwise $$$ans[i]$$$ is the character 'B'.
4 2 1 2 3 1 2 3 2 4 1 2 1 3 1 4 4 1 2 4 2 3 4
AA ABA AAAA AAAA
| Name |
|---|


