Symmetric Trees (Small)

You are given a tree with $N$ vertices, and each vertex has a 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 conditions below hold at once.

• No two vertices share a location.
• If vertex $v_i$ has color $C$ and location $(x_i, y_i)$, then a vertex $v_i'$ with color $C$ and location $(-x_i, y_i)$ also exists. 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 endpoints, two different segments share no point except an endpoint shared by two adjacent edges.

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

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

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

The next $N-1$ lines each contain two integers $i$ and $j$ ($1 \le i < j \le N$). This means 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 12$

For each test case, print one line in the form "Case #x: y", where $x$ is the test case number starting from $1$, and $y$ is SYMMETRIC if the tree is line symmetric by the definition above and NOT SYMMETRIC otherwise.

The first test case can be drawn like this.

No placement of the vertices of the second test case gives a line of symmetry.

One way to draw the third test case with a line of symmetry is shown below.