You are given an undirected tree of size $n$, where each edge has one of the labels: up, down, left, or right.

The tree represents a water piping system. Initially, the pipes are dry and we will choose one source node and start pumping water to it.

When water reaches a node through some edge, it will be pushed through all other edges. So for each edge, the water will flow in one direction only.

For a given source, the nodes must be positioned such that the edges will be oriented relative to the direction of the water. For example, if water flows from node $a$ to node $b$ through an edge with label "right", then node $b$ must be to the right of node $a$.

You can imagine it as drawing the tree on a 2D plane, first you place the source node, then place its adjacent nodes relative to it according to the labels of the edges, and so on. Nodes and edges can intersect and overlap.

The only constraint is that no node can have overlapping edges moving water from or to it, which means we need to choose the source such that the following two cases will not happen:

• Water flows from some node through two or more edges of the same label.
• Water flows from $a$ to $b$ through an edge of some label, and flows from $b$ to $c$ through an edge of the opposite label (up and down, or left and right). This is invalid because we have two overlapping edges moving water from or to $b$.

Find the possible sources where we can start pumping water without having overlapping edges moving water from or to the same node. It is guaranteed that the given tree will have at least one possible source.

The first line of input contains a single integer $T$ ($1 \le T \le 10^5$), the number of test cases.

The first line of each test case contains a single integer $n$ ($2 \le n \le 10^5$), the number of nodes in the tree.

Each of the following $n-1$ lines contains two integers $u$ and $v$ ($1 \le u,v \le n$), followed by one letter $c$ ($c \in $ {U, D, L, R}), representing an edge between the two nodes $u$ and $v$ with label $c$. The four letters {U, D, L, R} represent the directions up, down, left, and right, respectively.

It is guaranteed that the given graph is a tree, and it has at least one possible source where we can start pumping water.

The total sum of $n$ over all test cases doesn't exceed $10^6$.

For each test case, print the possible sources in increasing order, separated by at least one space, on a single line.

In the first test case, we can start at node $1$ or node $5$, in both cases we won't have overlapping edges of the same node. If we start at any other node, we will have two edges with label R going from the same node.