Expansion Order

Time limit1sMemory limit128 MB

Summary

Given sets of stations and a network that starts as station 1, output the lexicographically smallest build order where each set touches the network when built, or Impossible.

Level: Medium6 of 10
Topics: Graph, Greedy, Sorting, Implementation
Solved: No attempts yet

Problem

After choosing which set of routes to add to the transit system, the next question is the order in which to build these expansions. A new line is only useful if, at the moment it is built, it already touches the existing network. For example, extending a line to Monrovia is pointless if Monrovia is not yet connected to the rest of the system.

You are given the current network as a single starting point (station $1$ , which stands for the entire existing network) together with all proposed expansions. Each expansion is a new route described by the set of stations it would connect. A route may be built only if at least one of its stations already belongs to the network; once it is built, all of its stations become part of the network.

Determine an order in which to build the routes so that every route connects to the network at the time it is built, or report that no such order exists.

Input

The first line contains the number of data sets $K$ . Each data set has the following form:

The first line contains two integers $n$ and $m$ ( $1 \le n \le 500$ , $1 \le m \le 50$ ): $n$ is the total number of stations, where station $1$ represents the entire current network, and $m$ is the number of proposed new routes.
The next $m$ lines each describe one route. Line $i$ lists the stations in the set $S_i \subseteq \{1, \dots, n\}$ that route $i$ would connect, separated by spaces.

Output

For each data set, first print a line Data Set x:, where $x$ is the data set's number (starting from $1$ ).

Then print the routes in the order in which they should be built, one route number per line (routes are numbered $1$ to $m$ in the order they appear in the input). Each route must connect to the network at the time it is built.

If several valid orders exist, print the lexicographically smallest one: compare two orders at the first position where they differ, and prefer the order with the smaller route number at that position.

If no valid order exists, print Impossible instead of an ordering.

Separate consecutive data sets with a blank line.

Examples3

Example 1

Input

Expected output

Data Set 1:
Impossible

Data Set 2:
3
2
1
4

Example 2
Input
```
1
3 1
1 2 3
```
Expected output
```
Data Set 1:
1
```
Example 3
Input
```
1
3 1
2 3
```
Expected output
```
Data Set 1:
Impossible
```