Isomorphism of Graphs with Few Cycles

• Each vertex of G is of degree 1 or 3.
• There is exactly one vertex of degree 3 which is not an element of any cycle of G.
• Each other vertex of degree 3 is an element of just one cycle of G.

Figure 1. An example of 4 graphs with the given properties. Each graph has 14 vertices, 15 edges, and it contains 2 cycles. The only vertex of degree 3 which is not an element of a cycle is highlighted in orange. There is only one pair of isomorphic graphs: a) and c).

The task

Given a set S of graphs described above, identify maximum subsets of isomorphic graphs contained in S.

Input

The first line of the input consists of integers T, N, M separated by space. T is the number of the input graphs, N is the number of vertices of each graph and M and is the number of edges of each graph. Next, there are T×M lines with pairs of integers V₁, V₂ representing an undirected edge {V₁, V₂}. Edges of the i-th graph are represented by lines from 1+(i−1)×M to i×M (provided the first edge of the first graph is at line 1). For each graph, its vertices are numbered from 1 to N and the edges are listed in a random order.
It holds 1 ≤ T ≤ 200 and N, M ≤ 65000.

Output

Let {G₁, ..., G_k} be a maximum subset of pairwise non-isomorphic input graphs. Let c_i be the number of input graphs isomorphic with G_i. The output contains one text line with all the numbers c_i sorted in ascending order and separated by spaces.

2 8 8
8 2
2 5
1 8
4 7
2 4
8 4
6 5
3 5
1 3
6 5
5 4
4 7
8 3
5 1
3 2
1 4

2

4 14 15
1 2
2 13
13 14
13 11
12 11
11 10
2 10
9 8
8 10
8 3
4 7
6 5
3 6
3 4
6 4
13 12
12 11
11 14
1 2
2 3
4 2
10 11
10 12
10 9
8 7
5 6
4 5
5 7
7 9
9 4
3 4

5 3
5 2
2 1
3 2
5 6
7 6
8 6
13 14
12 11
10 9
8 14
11 14
9 8
9 11
1 8
1 2
1 10
9 8
9 13
9 10
7 8
11 10
13 14
12 13
2 5
5 6
5 3
2 3
4 3

1 1 2

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set