|
Название задачи: Кошки-Мышки . |
 |
Условие
Игровое поле для игры «Кошки-мышки» представляет собой совокупность кружков, некоторые из которых соединены линиями. Первый игрок играет за «кошек», второй – за «мышек». В процессе игры кошки и мышки располагаются в кружках игрового поля. Ходы совершаются игроками по очереди. За один ход игрок может передвинуть некоторые из своих фигур (кошек или мышек) по линиям, ведущим из тех кружков, где они в данный момент находятся. Первыми ходят кошки. В случае если кошка окажется в одном кружке с мышкой, мышка считается съеденной. Цель первого игрока – съесть максимальное число мышек и сделать это как можно быстрее, цель второго – помешать первому игроку. Напишите программу, определяющую максимальное число мышек, которых
съедят кошки, и номер хода, на котором будет съедена последняя из них, в
предположении о наилучших действиях обоих игроков.
Входные данные
В первой строке входного файла содержатся два целых числа N и M –
количество кружков (1 ≤ N ≤ 20) и линий (1 ≤ M ≤
200) на игровом поле. В следующих M строках указаны номера кружков, которые соединяются
очередной линией. Далее следуют количество кошек и номера кружков, в
которых они первоначально располагаются. После этого в таком же формате
записаны данные о мышках. Суммарное количество кошек и мышек не
превосходит четырех.
Выходные данные
Запишите в выходной файл максимальное количество мышек, съедаемых
кошками, минимальное число ходов, необходимых для этого, и все возможные
положения кошек после первого хода, обеспечивающие достижение цели за
указанное число ходов.
Пример входного файла
8 9
1 2
2 3
3 4
4 1
1 5
5 6
6 7
7 8
8 6
1 5
2 3 7
Пример выходного файла
1 2
6
