Symmetric Trees (Large)

You are given a tree with $N$ vertices, and every vertex is painted with one color. Decide whether the tree can be drawn in the plane so that it has a line of symmetry.

Formally, a tree is line symmetric if every vertex can be assigned a location in the plane so that all four of the following hold.

• All locations are distinct.
• If vertex $v_i$ has color $C$ and coordinates $(x_i, y_i)$, then there is also a vertex $v_i'$ of color $C$ at $(-x_i, y_i)$. If $x_i$ is 0, then $v_i$ and $v_i'$ are the same vertex.
• If edge $(v_i, v_j)$ exists, then edge $(v_i', v_j')$ also exists.
• When each edge is drawn as the straight segment between its two end vertices, two different edges share no point. Two adjacent edges meeting at their common endpoint are allowed.

The first line holds the number of test cases $T$. The test cases follow.

The first line of each test case holds $N$, the number of vertices in the tree.

The next $N$ lines each hold one uppercase letter. The $i$-th of them is the color of vertex $i$.

The next $N-1$ lines each hold two integers $i$ and $j$ ($1 \le i < j \le N$), meaning that the tree has an edge between vertex $i$ and vertex $j$. The given edges always form a connected tree.

Limits:

• $1 \le T \le 100$
• $2 \le N \le 10000$

For each test case, print one line holding Case #x: y, where x is the test case number starting from 1, and y is SYMMETRIC when the tree is line symmetric by the definition above and NOT SYMMETRIC when it is not.

The first test case of the sample input can be drawn like this.

No arrangement of the second test case has a line of symmetry.

Here is one way to draw the third test case with a line of symmetry.