hackercupai/hackercup huggingface dataset:
Recently, Melody built a little boat, as cute as it could be. And she put a
number of animals, two-by-two, on her little boat on the sea!

Melody's boat features **N** rooms, numbered from 1 to **N**. The contents of
the _i_th room are described by the string **Ai**. If **Ai** = "-", then the
room is empty, while otherwise the room contains an animal of species **Ai**
(where **Ai** is a case-sensitive alphanumeric string made up of lowercase
letters "a"..."z", uppercase letters "A"..."Z", and digits "0"..."9"). There
are **at most two animals of any given species** on the boat.

There are **N**-1 corridors in the boat, the _i_th of which allows Melody and
the animals to travel in either direction between rooms **Xi** and **Yi**.
Each room is reachable from each other room by following a sequence of
corridors.

It's time for Melody's daily walk through her boat! She'd like to choose one
room to start in and a different room to end in, and walk from the former to
the latter. She'll take the unique path which allows her to do so without
visiting any room multiple times. Along the way, any time she finds herself in
a room containing an animal (including the starting or ending room), that
animal will join her for the remainder of her walk. Normally, both Melody and
the animals will keep quiet, which is just how she likes it. However, if two
animals of any given species ever end up joining her, they'll promptly make a
racket talking to one another, which is no good! As such, she'll refuse to
take a walk which would result in encountering two of any species of animal.

For how many of the **N***(**N**-1) possible ordered pairs of starting/ending
rooms would it be possible for Melody to enjoy a quiet walk from one to the
other?

### Input

Input begins with an integer **T**, the number of boats.
For each boat, there is first a line containing the integer **N**.
Then, **N** lines follow, the _i_th of which contains the string **Ai**.
Then, **N** \- 1 lines follow, the _i_th of which contains the space-separated
integers **Xi** and **Yi**.

### Output

For the _i_th boat, print a line containing "Case #_i_: " followed by one
integer, the number of valid ordered pairs of starting and ending rooms for
Melody's walk.

### Constraints

1 ≤ **T** ≤ 95
2 ≤ **N** ≤ 800,000
1 ≤ **Xi**, **Yi** ≤ **N**
1 ≤ |**Ai**| ≤ 10

The sum of **N** across all **T** test cases is no greater than 4,000,000.

### Explanation of Sample

In the first case, the 4 starting/ending room pairs (1, 2), (2, 1), (2, 3),
and (3, 2) are valid. On the other hand, the pairs (1, 3) and (3, 1) are not.
For example, on the way from room 1 to room 3, a Fox would begin following
Melody around in room 1, and upon being joined by another Fox in room 3, the
two Foxen would begin making strange noises towards one another.

In the second case, both possible starting/ending room pairs ((1, 2) and (2,
1)) are no good, as they would involve encountering two talkative Turtles.

In the third case, both possible starting/ending room pairs will do, as no two
animals of any given species can be encountered.