hackercupai/hackercup huggingface dataset:
You have \(N\) [tries](https://en.wikipedia.org/wiki/Trie). The \(i\)th trie has \(M_i\) nodes and \(M_i - 1\) edges, with node \(1\) being the root, and node \(j\)'s parent being \(P_{i,j}\), for \(j = 2..M_i\). Edge \(P_{i,j} \to j\) is labeled with a lowercase letter \(C_{i,j}\).

We say a string is *in* a trie if it can be formed by concatenating the letters along some path starting at the root and ending at some node (either internal or leaf).

For every possible unordered triplet of these \(N\) tries, you would like to know: how many strings exist which are in at least one of the three tries?

Please print the sum of answers over all \(N*(N-1)*(N-2)/6\) possible queries.

# Constraints

\(1 \le T \le 100\)
\(3 \le N \le 100\)
\(1 \le M_i \le 1{,}000{,}000\)
\(1 \le P_{i,j} \lt j\)
\(C_{i,j} \in \{\)`'a'`\(,\, \ldots, \) `'z'`\(\}\)

The sum of \(N\) across all cases is at most \(2{,}000\).
No node will have two direct outgoing edges with the same edge label.
There are at most \(1{,}000{,}000\) total trie nodes in a given test case.
The sum of nodes across all test cases is at most \(13{,}000{,}000\).

# Input Format

Input begins with a single integer \(T\), the number of test cases. For each test case, there is first a line containing a single integer \(N\), the number of tries. Then, \(N\) descriptions of tries follow. For the \(i\)th trie, there is first a line containing a single integer \(M_i\), followed by \(M_i - 1\) more lines, the \(j\)th of which contains the integer \(P_{i,j+1}\), followed by a space, followed by the letter \(C_{i,j+1}\).

# Output Format

For the \(i\)th test case, output a single line containing `"Case #i: "` followed by a single integer, the sum of the query answers across all triplets of tries.

# Sample Explanation

In the first case, there are \(N = 3\) tries, depicted below:

{{PHOTO_ID:502671685043623|WIDTH:650}}

There is only one possible unordered triplet of tries to consider, for which there are \(5\) strings in at least one trie of the triplet: "", "`a`", "`aa`", "`b`", and "`c`".

In the second case, there are \(N = 4\) tries, depicted below:

{{PHOTO_ID:1118217749060271|WIDTH:650}}

There are four triplets of tries to consider, three of which include the last trie and one of which doesn't. In the three that does, there are \(4\) strings in at least one trie: "", "`a`", "`aa`", and "`aaa`". In the one that doesn't, the are \(2\) strings: "" and "`a`". The final answer is \(3*4 + 1*2 = 14\).

In the third case, there are \(N = 4\) tries, depicted below:

{{PHOTO_ID:1007664223967563|WIDTH:650}}

The four triplets and strings contributing to the answer are:
* \((\)trie \(1\), trie \(2\), trie \(3)\): "", "`a`", "`b`", "`c`"
* \((\)trie \(1\), trie \(2\), trie \(4)\): "", "`a`", "`b`", "`ab`", "`abc`"
* \((\)trie \(1\), trie \(3\), trie \(4)\): "", "`a`", "`c`", "`ab`", "`abc`"
* \((\)trie \(2\), trie \(3\), trie \(4)\): "", "`a`", "`b`", "`c`", "`ab`", "`abc`"

The final answer is \(4 + 5 + 5 + 6 = 20\).