Isomorphism of Tree-Cycle Graphs

• E=E_t ∪ E_c where E_t ∩ E_c = ∅ and |E_c| ≥ 2,
• G_t=(V, E_t) is a directed rooted tree,
• there is C ⊆ V of size |E_c| such that G_c=(C, E_c) is a cycle of length |E_c|,
• each path from the root of G_t to a leaf of G_t contains exactly one node of C.

Figure 1. An example of 4 tree-cycle graphs with 7 nodes and 9 edges. Edges of the cycle subgraphs Gc are drawn in blue. There is only one pair of isomorphic graphs: a) and d).

The task

Given a set of tree-cycle graphs with the same number of nodes and edges, identify how many mutually non-isomorphic tree-cycle graphs are contained in the set.

Input

The first line of the input is formed of three integers T, N, M separated by space. T is the number of tree-cycle graphs in the input, N is the number of nodes in each graph and M and is the number of edges in each graph. Next, there are T×M lines with pairs of integers V₁, V₂ representing a directed 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, the nodes are numbered from 1 to N and the edges are listed in a random.
It holds T ≤ 300, M, N ≤ 68000.

Output

Let {G₁, ..., G_k} be a maximal subset of mutually 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 non-descending order and separated by spaces.

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

2

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

1 1

4 7 9
1 2
1 3
1 4
2 3
3 4
4 2
2 5
3 6
4 7
1 2
2 5
1 3
3 6
1 4
4 7
2 3
7 2
3 7
1 2
1 3
1 4
2 5
2 4
3 7
4 7
7 2
2 6
1 2
2 3
3 4
1 3
4 2
1 4
2 5
3 6
4 7

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