Зоопарк Глеба
(Время: 1 сек. Память: 16 Мб Сложность: 46%)
Недавно Глеб открыл свой зоопарк. По лучшим мировым традициям он имеет форму круга, впрочем это не важно. Важно то, что он взял вас туда начальником охраны. Казалось бы все началось так хорошо, но именно в вашу первую смену кто-то открыл все клетки и животные разбежались по всему зоопарку. Перед вами встала задача поймать всех животных в ловушки, чтобы потом вернуть каждого в свою клетку.
В зоопарке n различных животных одного из 26 видов. Каждый вид обозначается своей буквой от 'a' до 'z'. Под каждый из них есть свой тип ловушки. Ловушки обозначаются латинскими заглавными буквами. К сожалению, почти все животные враждуют между собой в природе, поэтому ни одно животное не станет переходить дорогу животному своего или другого вида из-за инстинкта самосохранения.
Зоопарк по периметру обнесен колючей проволокой, поэтому животные не могут ходить вдоль забора.
С помощью камер, удалось выяснить, где находятся все животные. Умная система поддержки жизнедеятельности зоопарка уже просканировала зоопарк и вывела типы всех животных и ловушек в том порядке, в котором они видны из центра зоопарка против часовой стрелки. Получилось так, что все животные и все ловушки находятся около забора, то есть можно считать, что путь любого животного начинается в одной из точек окружности и заканчивается в точке, где находится ловушка для животных этого вида - тоже точка на окружности.
Вы хотите понять, могут ли животные придти в свою ловушку так, чтобы их путь не пересекался ни с одним другим. Если да, выведите какую-нибудь из схем поимки животных.
Входные данные
Входной файл INPUT.TXT содержит строку, состоящую из 2×n символов латинского алфавита, где маленькая буква - животное, а большая - ловушка. Здесь n (1 ≤ n ≤ 10000) - количество животных и ловушек. Гарантируется, что ловушек каждого типа столько же, сколько и представителей данного вида животных в зоопарке.
Выходные данные
В выходной файл OUTPUT.TXT выведите "Impossible", если решения не существует или "Possible", если можно загнать всех животных в свои ловушки так, чтобы их пути не пересекались.
Если это возможно, то для каждой ловушки в порядке обхода требуется вывести индекс животного, которое будет поймано в ней. Индексом животного называется его порядковый номер среди животных в общем списке животных и ловушек.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | ABba | Possible 2 1 |
2 | ABab | Impossible |
Пояснения к примерам
В первом примере животное b идёт в ловушку B, а животное a ловится в ловушку A. Их пути не пересекаются, поэтому их возможно поймать.
Во втором примере пути животных в любом случае пересекаются, поэтому поймать их невозможно.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|