20262번 - Graph Cards 다국어

A deck of graph cards is placed on the table. Each graph card χ is decorated with an undirected simple graph G_χ so that G_x is connected and G_χ has the same number of nodes and edges. Note that different graph cards may have different numbers of nodes. An example is depicted as follows.

We say two graph cards are identical if and only if the graphs associated with them, say G₁ = (V₁, E₁) and G₂ = (V₂, E₂), are isomorphism; that is, there exists a bijection f between the node sets V₁ and V₂ so that for every x, y ∈ V₁, edge (x, y) ∈ E₁ if and only if edge (f(x), f(y)) ∈ E₂. Our goal is to compute the number of distinct graph cards in the deck.

The first line contains an integer t that indicates the number of test cases. For each test case, you are given a deck of graph cards. It begins with a line containing the number of graph cards n > 0. Then, n lines follow. Each line represents a graph card associated with a graph G in the following format:

k u₁ v₁ u₂ v₂ · · · u_k v_k

where k > 0 denotes the number of nodes (also edges) in G and for each i ∈ [1, k] (u_i, v_i) denotes an edge in G that connects nodes u_i and v_i. Note that the identifiers of nodes are integers in [1, k].

For each test case, output the number of distinct graph cards in the given deck on a line.

• 0 < t ≤ 30.
• 0 < n, k ≤ 10⁶.
• For each test case, the numbers of nodes in the n graph cards sum up to at most 10⁶.