Basin City Surveillance

BASIN CITY has a very high crime rate. The police are tightening security and want to install traffic drones at intersections to watch for cars running a red light. When a car runs a red light, the drone at that intersection chases the car, stops it, and gives the driver a ticket.

The drones are not smart. A drone breaks off a chase before it reaches the next intersection, because any farther out it would lose the way back to its home, the traffic light it is assigned to. A drone also cannot detect another drone, so the police R&D department concluded that once a drone sits at an intersection, no drone should be placed at an intersection joined to it by a road. As in many other cities, no intersection in BASIN CITY has more than four neighbouring intersections.

The government pays for the drones, so the police want to buy as many as they are allowed to. Given the number of drones $k$, decide whether exactly $k$ drones can be placed so that no two of them sit at neighbouring intersections.

The first line contains the number of drones to place, $k$ ($0 \le k \le 15$). The second line contains the number of intersections in BASIN CITY, $n$ ($1 \le n \le 100\,000$). The next $n$ lines describe the intersections in order. The $i$-th of those lines starts with an integer $d$, the number of intersections neighbouring intersection $i$ ($0 \le d \le 4$), followed by the $d$ indices of those neighbours. The indices are distinct and different from $i$. The intersections are numbered from 1 to $n$.

Print possible on a single line if $k$ drones can be placed so that no two neighbouring intersections both hold a drone. Otherwise print impossible.