Пірати
Корабель зазнав нападу піратів. Він знаходиться приблизно за 30 хвилин від найближчого військового флоту, який прямує на допомогу. Екіпаж зібрався в безпечній зоні корабля. Капітан прагне захистити цю зону, щоб уникнути захоплення піратами, що ускладнить рятувальну операцію. На кораблі є багато зон, з'єднаних дверима. Кожні двері можуть бути замкнені або відчинені лише з одного боку. Пірати захопили деякі зони, і капітан хоче замкнути мінімальну кількість дверей, щоб пірати не змогли проникнути в безпечну зону. Наприклад, у наступному сценарії зображено корабель з 7 зонами:
Кімнати пронумеровані від 0 до 6, і '*' позначає сторону дверей, з якої їх можна замкнути або відчинити. Якщо екіпаж знаходиться в зоні 4, а всі пірати в зоні 5, щоб захистити екіпаж, капітану потрібно замкнути щонайменше двоє дверей: між зонами 3 і 5, та між зонами 4 і 5. Зверніть увагу, що замикання дверей між зонами 3 і 4 замість дверей між зонами 3 і 5 є помилкою, оскільки пірати можуть легко відчинити двері між зонами 3 і 4 та проникнути в безпечну зону.
Вхідні дані
Вхідні дані містять кілька тестових випадків. Кожен тестовий випадок починається з рядка, що містить два невід'ємні цілі числа z і s (0 ≤ z ≤ 20, 0 ≤ s ≤ 19), де z вказує кількість зон на кораблі, а s — номер безпечної зони. Зони пронумеровані від 0 до z−1. На наступних z рядках i-й рядок представляє інформацію для зони i−1. Кожен рядок починається з 'P' або 'NP', де 'P' означає, що зона зайнята піратами, а 'NP' означає, що зона ще чиста. Після 'P'/'NP' вказується кількість дверей, які можна замкнути/відчинити зсередини зони i−1. Рядок продовжується списком зон, до яких можна дістатися через ці двері. Наприклад, у наведеному вище прикладі ми не перераховуємо зони 3 і 4 у рядку, що представляє зону 5, оскільки двері, що прилягають до зон 3 і 4, не можуть бути замкнені/відчинені зсередини зони 5. Вихід завершується "0 0", що не повинно оброблятися.
Вихідні дані
Для кожного тестового випадку виведіть мінімальну кількість дверей, які потрібно замкнути, щоб захистити безпечну зону. Якщо неможливо забезпечити безпеку безпечної зони, просто виведіть "Вибачте, капітане!". Припустимо, що всі двері відчинені на початку, і в безпечній зоні немає жодного пірата.