H. 3awatleyyet El ASU
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

"Powerpuff men" and "1234" were rewarded the prize of #1 & #2 3awatleyyeh groups in ASU; therefore they thought of opening an online non-existent company and call themselves CEOs of 3awatleyyeh Co.

3awatleyyeh Co. is a company with no tasks, they only spam LinkedIn with fake achievements and success stories posts plus calling themselves El 7eetan to advertise themselves. They decided to do another useless activity together since they have nothing to do in their lives.

The activity is as follows: they wanted to compare their family trees and check what is the maximum occurrences of similar family tree structures, with the oldest known ancestors they remember as the roots of the tree, at least going back to their four grandparents. Each node in the tree has a value, either M or F. M for a Male, F for a Female.

Each person (except the roots) has exactly two parents, and no two parents of the same child share a common ancestor. The family tree is represented as a directed acyclic graph (DAG), with edges directed from parent to child. Two family trees are considered identical if they have the same structure and the same labels at every corresponding node.

Since they are lazy brain-rotted individuals, they hired you to do this task for them.

Input

The first line contains a single integer $$$n$$$ – the number of 3awatleyyeh $$$(1 \leq n \leq 10^4)$$$.

For each of the $$$n$$$ family trees:

  • A line containing a single integer $$$s$$$ – the number of people in this family tree $$$(7 \leq s \leq 10^3)$$$.
  • A line containing $$$s$$$ space-separated characters, the $$$i$$$-th being the label of node $$$i$$$ (0-indexed), either M or F.
  • A line containing a single integer $$$e$$$ – the number of edges $$$(2 \leq e \leq s(s-1)/2)$$$.
  • $$$e$$$ lines, each containing two integers $$$u$$$ and $$$v$$$ $$$(0 \leq u, v \lt s)$$$, representing a directed edge from parent $$$u$$$ to child $$$v$$$.

It is guaranteed that:

  • Every root node has no parents and represents an oldest known ancestor.
  • Every non-root node has exactly two parents.
  • No two parents of the same child share a common ancestor.
  • The graph contains no cycles.
Output

Print a single integer – the maximum number of identical family trees among the $$$n$$$ given trees.

Example
Input
4
7
M F M F M F M
6
0 4
1 4
2 5
3 5
4 6
5 6
7
M F M F M F M
6
4 6
2 5
1 4
5 6
3 5
0 4
7
M F M F M F M
6
2 5
0 4
3 5
4 6
1 4
5 6
7
F M F M F M F
6
0 4
1 4
2 5
3 5
4 6
5 6
Output
3
Note

The first three family trees are structurally identical with matching labels – the edges are listed in a different order in the input for each, but the underlying structure is the same. The fourth tree has all labels swapped (F where M was and vice versa), making it different from the rest. Therefore the answer is $$$3$$$.