패닉 룸

당신은 Jellern Inc.가 만든 홈 보안 시스템 Securitron 9042의 수석 프로그래머입니다(사훈: 당신의 물건을 당신조차 꺼낼 수 없도록 지켜 드립니다). 이 시스템은 어떤 방을 지키기 위해, 침입자가 그 방에 도달하지 못하도록 최소한의 문만 잠급니다. 지켜야 하는 그 방을 패닉 룸이라고 부릅니다.

모든 문은 정확히 두 개의 방을 연결하며, 하나의 제어판으로만 열립니다. 각 제어판은 문이 연결하는 두 방 중 한쪽 방 안에만 있으며, 문은 그 방에서만 잠금을 해제할 수 있습니다. 여기서 두 가지 규칙이 나옵니다.

• 어떤 문의 제어판이 있는 방에 있는 사람은 언제나 그 문을 열고 반대쪽 방으로 건너갈 수 있습니다. 문을 잠가도 소용이 없습니다. 그냥 다시 잠금을 해제하면 되기 때문입니다.
• 반대쪽 방(제어판이 없는 쪽)에 있는 사람은 문이 열려 있을 때만 통과할 수 있습니다. 이런 문을 잠그면 그 사람은 통과하지 못합니다. 제어판에 접근해 다시 열 수 없기 때문입니다.

모든 문은 처음에 열려 있습니다. 집의 구조, 현재 침입자가 있는 방들, 그리고 패닉 룸이 주어집니다. 어떤 침입자도 패닉 룸에 도달하지 못하게 하려고 잠가야 하는 문의 최소 개수를 출력하세요.

불가능할 수도 있습니다. 예를 들어 어떤 침입자가, 패닉 룸으로 바로 통하는 문의 제어판이 있는 방에 있다면, 그 침입자는 언제나 그 문을 열고 들어올 수 있으므로 패닉 룸을 지킬 수 없습니다.

첫 번째 줄에는 데이터셋의 개수 $x$가 주어집니다. 각 데이터셋은 다음과 같습니다.

• 두 정수 $m$과 $n$이 있는 한 줄 ($1 \le m \le 20$, $0 \le n \le 19$): $m$은 방의 개수, $n$은 지켜야 할 패닉 룸입니다. 방은 $0$번부터 $m-1$번까지 번호가 매겨집니다.
• 이어서 방을 순서대로 설명하는 $m$개의 줄이 옵니다. $i$번째 줄(0부터 시작)은 방 $i$를 설명합니다. 각 줄에는 공백으로 구분되어 다음이 주어집니다.
  • 그 방에 침입자가 있으면 I, 없으면 NI;
  • 제어판이 이 방에 있는 문의 개수 $c$ ($0 \le c \le 20$);
  • 그 문들의 반대편 방 번호 $c$개(오름차순으로 나열).

두 방이 여러 개의 문으로 연결될 수 있고, 침입자가 여러 명일 수도 있습니다. 패닉 룸에는 침입자가 없습니다.

각 데이터셋마다, 어떤 침입자도 패닉 룸에 도달하지 못하도록 잠가야 하는 문의 최소 개수를 한 줄에 출력하세요. 어떤 방법으로도 패닉 룸을 지킬 수 없다면 대신 PANIC ROOM BREACH를 출력하세요.