Pirates#6900

Pirates

1 second

64 megabytes

Hard

A ship has been attacked by pirates. The ship is within the distance of about $30$ minutes from the nearest navy, who are approaching to rescue them. The ship's crews have gathered in the safe zone of the ship. The captain wants to secure the safe zone in order to prevent the pirates from taking them as hostages, which makes the situation more complicated for the rescuers. The ship has many zones connected by some doors. Each door can be locked and unlocked from just one side of the door. The pirates have occupied some of the ship's zones, and the captain wants to lock the minimum number of doors in order to prevent the pirates entering the safe zone. For example, in the following setting, a ship with $7$ zones is depicted:

Rooms are numbered from $0$ through $6$ , and a ' $*$ ' is shown in one side of each door denoting the door can be locked/unlocked from that side. If the crews are in Zone $4$ and all pirates are in Zone $5$ , to protect the crews, the captain needs to lock at least two doors, namely the door between Zones $3$ and $5$ , and the door between Zones $4$ and $5$ . Note that locking the door between Zones $3$ and $4$ instead of the door between Zones $3$ and $5$ is a big mistake, as the pirates can easily unlock the door between Zones $3$ and $4$ and enter the safe zone.

Input

There are multiple test cases in the input. Each test case starts with a line containing two non-negative integers $z$ and $s$ ( $0 \leq z \leq 20$ 0 \leq z \leq 20, $0 \leq s \leq 19$ 0 \leq s \leq 19), where $z$ indicates the number of zones in the ship and $s$ is the number of the safe zone. Suppose zones are numbered from $0$ through $z - 1$ z-1. On the following $z$ lines, the ith line represents the information for Zone $i - 1$ i-1. Each line starts with either ' $P$ ' or ' $N P$ ', where ' $P$ ' means the zone has been occupied by some pirates, and ' $N P$ ' means the zone is still clean. After ' $P$ '/' $N P$ ', the number of doors which are lock/unlock-able from inside Zone $i - 1$ i-1 appears. The line is followed with the list of reachable zones from these doors. For instance, in the above example, we don't list Zones $3$ and $4$ in the line representing Zone $5$ , because the doors being adjacent to Zones $3$ and $4$ are not lock/unlock-able from inside zone $5$ . The input terminates with " $0$ $0$ " which should not be processed.

Output

For each test case, output the minimum number of doors which must be locked in order to protect the safe zone. If it is impossible to secure the safe zone, just output "Sorry Captain!". Assume that all doors are open at the beginning, and there is not any pirate in the safe zone.

Examples

Example 1