Identical Carnival Maze Rooms

Jay runs a carnival with a large, twisting maze consisting of circular rooms connected by corridors. Each room is circular with its corridors (exits) arranged evenly around it. The only distinguishing characteristic of a room is its number of exits. However, even if two rooms have the same number of exits, they may be effectively different because of the way corridors connect to other rooms.

Two rooms A and B are considered effectively identical if, when dropped into either room (with a complete map of the maze in hand), one cannot tell which room they started in by exploring the maze. When you enter a room you know which corridor you came from, so you can follow the circular ordering of exits. In other words, if the circular orders of the equivalence classes of the neighboring rooms are the same (up to a rotation), then the two rooms are effectively identical.

Your task is to identify all the sets of effectively identical rooms in the maze. Note that only groups of two or more rooms should be reported (a single room on its own is not redundant). For each test case, output each equivalence set as a sorted sequence of room indices (0-indexed), and print the sets in increasing order of their smallest room index. If no pair of effectively identical rooms exists, simply output none.

The equivalence is defined in a bisimulation style: Initially, rooms are distinguished solely by their number of exits. Then, iteratively, two rooms become equivalent only if their lists of neighbor equivalence classes (when viewed as a cyclic sequence and compared up to rotation) are the same. This refinement is carried out until no further change occurs.

Note: If a room has d exits, and its neighbors’ current equivalence classes form the sequence \(a_0,a_1,\dots,a_{d-1}\), then the canonical form for that room is defined as \(\min_{0\le r < d} (a_r,a_{r+1},\dots,a_{d-1},a_0,\dots,a_{r-1})\) in lexicographic order. Two rooms are equivalent if and only if they have the same exit count and the same canonical form.

inputFormat

The input begins with a single integer \(T\) (\(1 \le T \le 10\)), the number of test cases. Each test case is described as follows:

• The first line contains an integer \(n\) (\(1 \le n \le 1000\)), the number of rooms.
• Then follow \(n\) lines; the \(i\)th line (0-indexed) describes room \(i\). Each such line begins with an integer \(d\) (\(0 \le d \le 10\)), the number of exits of the room, followed by \(d\) integers. These \(d\) integers represent the room indices that are reached by taking each exit in clockwise order.

You may assume that the corridors are bidirectional so that if room A lists B as a neighbor then room B will list A in its description. Rooms are 0-indexed.

outputFormat

For each test case, output the sets of effectively identical rooms as follows:

• If there exists at least one set of two or more identical rooms, then for each such set, output a line containing the room indices (in increasing order) separated by a single space. The sets should appear in increasing order of their smallest room index.
• If no such set exists, output a single line with the word none.

If there are multiple test cases, separate the outputs for consecutive test cases with a blank line.

sample

3
4
2 1 2
2 0 3
2 0 3
1 1
3
2 1 2
2 0 2
2 0 1
1
1 0

1 2
0 1 2
none