Panic Room

You are the lead programmer for the Securitron 9042, the home-security system built by Jellern Inc. (motto: We secure your stuff so you can't even get to it). The system secures a room by locking as few doors as possible so that no intruder can reach it. That room is called the panic room.

Every door connects exactly two rooms and is opened by a single control panel. Each control panel sits inside just one of the two rooms the door connects, and the door can only be unlocked from that room. This leads to two rules:

• Someone standing in the room that holds a door's control panel can always open that door and step through to the other room. Locking the door does not stop them — they simply unlock it again.
• Someone on the other side (the room without the control panel) can pass through the door only while it is unlocked. Locking such a door stops them, because they cannot reach the panel to reopen it.

All doors start unlocked. You are given the layout of the house, which rooms currently hold an intruder, and which room is the panic room. Output the minimum number of doors you must lock so that no intruder can reach the panic room.

It can be impossible. For instance, if an intruder stands in a room that holds the control panel of a door leading straight into the panic room, that intruder can always unlock it and walk in, so the room cannot be secured.

The first line contains an integer $x$, the number of datasets. Each dataset is:

• A line with two integers $m$ and $n$ ($1 \le m \le 20$, $0 \le n \le 19$): $m$ is the number of rooms and $n$ is the panic room to secure. Rooms are numbered from $0$ to $m-1$.
• Then $m$ lines describing the rooms in order — line $i$ (0-indexed) describes room $i$. Each line contains, separated by spaces:
  • I if there is an intruder in that room, or NI if there is not;
  • an integer $c$ ($0 \le c \le 20$), the number of doors whose control panel is in this room;
  • the $c$ room numbers on the other side of those doors, listed in ascending order.

Two rooms may be connected by more than one door, and there may be more than one intruder. There is never an intruder in the panic room.

For each dataset, print on its own line the smallest number of doors that must be locked so that no intruder can reach the panic room. If no set of locks can secure it, print PANIC ROOM BREACH instead.