Graph Cards

A deck of graph cards is placed on the table. Each graph card $\chi$ is decorated with an undirected simple graph $G_\chi$. Each $G_\chi$ is connected and has the same number of nodes and edges. Different graph cards may have different numbers of nodes.

Two graph cards are identical if and only if their graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ are isomorphic. That is, there is a bijection $f$ from $V_1$ to $V_2$ such that for all $x, y \in V_1$, $(x, y) \in E_1$ if and only if $(f(x), f(y)) \in E_2$. The goal is to count the distinct graph cards in the deck.

The first line contains an integer $t$, the number of test cases. Each test case begins with a line containing the number of graph cards $n > 0$. Then $n$ lines follow, each describing one graph card in this format:

k u1 v1 u2 v2 ... uk vk

Here $k > 0$ is the number of nodes, which is also the number of edges. For each $i \in [1, k]$, $(u_i, v_i)$ is an edge. Node identifiers are integers in $[1, k]$.

For each test case, print the number of distinct graph cards in the deck on its own line.

• $0 < t \le 30$
• $0 < n, k \le 10^6$
• For each test case, the node counts of the $n$ graph cards sum to at most $10^6$.