Задача №114660. Розыск преступной банды
Это интерактивная задача.
В некотором городе завелась преступная банда, которая по ночам грабит банки. Правительство решило обратиться к помощи программистов для вычисления местоположения преступников. Вы один из тех, кому предстоит помочь установить спокойствие в городе.
В городе есть \(n\) перекрёстков, пронумерованных целыми числами от \(1\) до \(n\), соединенных \(n-1\) двусторонней улицей. При этом от любого перекрёстка можно доехать до любого другого по улицам единственным образом. Иными словами, система улиц представляет собой дерево.
Банда преступников состоит из нескольких человек, содержит не меньше \(1\) и не больше \(10\) человек. Каждый преступник живет около некоторого перекрёстка, все преступники живут около разных перекрёстков. Также известно, что ни один из преступников не живет на простом пути между перекрёстками, около которых живут два других преступника. За счет этого банде легче осуществлять свои планы.
Каждый день полиция может установить особо тщательную слежку за некоторой частью города. Это означает, что некоторые перекрёстки города будут контролироваться. При этом слежку можно устанавливать над перекрёстками, которые образуют некоторый связный подграф в дереве улиц города, то есть над любым перекрёстком, лежащем на простом пути между двумя перекрёстками, над которыми ведется слежка, тоже ведется слежка. После этого, ночью этого дня, если над всеми перекрёстками, на которых живут преступники, ведется слежка, то ограбления не произойдет, иначе произойдет.
Поняв, что из этого можно получить некоторую информацию о местоположении преступников, правительство обратилось за помощью программистов. Вы можете задавать перекрёстки, за которыми надо установить слежку в следующий день. После этого вам сообщат произошло ли ночью ограбление или нет. Несколько раз используя это, вы должны вычислить номера всех перекрёстков, около которых живут преступники. К сожалению, до следующих выборов мэра города осталось ровно \(100\) дней, а правительство очень хочет показать городу свою силу и разыскать всех преступников. Помогите правительству и напишите программу, которая за не более, чем \(100\) дней, определит положения всех преступников.
Сначала вашей программе на вход подается описание города. В первой строке находится единственное целое число \(n\) (\(1 \leq n \leq 1000\)) — количество перекрёстков в городе. В следующих \(n-1\) строках записано по два целых числа \(s\) и \(f\) (\(1 \leq s, f \leq n, s \neq f\)) — номера перекрёстков, соединенных очередной улицей. Гарантируется, что представленная система улиц образует дерево.
После этого вам предстоит несколько раз решить задачу поиска местоположений преступников. В начале вам будет дан один символ, который равен либо « S », либо « E ». Если символ равен « E », то это означает, что больше ваша программа не должна решать задачу поиска местоположений преступников и должна немедленно завершиться. Если символ равен « S », то ваша программа должна начать решать очередную такую задачу и может начинать делать запросы.
Для того, чтобы установить слежку над некоторым множеством перекрёстков, ваша программа должна вывести « \(? \, k \, v_1 \, v_2 \, \ldots \, v_k\) », где \(1 \leq k, v_i \leq n\), все \(v_i\) различны. Этот запрос означает, что за множеством перекрёстков \(\{v_1, v_2, \ldots, v_k\}\) нужно установить слежку. Это множество перекрёстков должно образовывать связный подграф (определение дано в условии задачи). В ответ ваша программа получит \(-1\), \(0\) или \(1\). Если ваша программа получит \(1\), то это означает, что ночью ограбления не произошло, если получит \(0\), то это означает, что ночью ограбление произошло. Если ваша программа получит \(-1\), это означает, что она нарушила формат выходных данных или сделала более \(100\) таких запросов. В этом случае она должна немедленно завершиться и получит вердикт « Неправильный ответ ». В противном случае вердикт, полученный таким решением, может быть любым.
Для того, чтобы вывести угаданное множество местоположений преступников, ваша программа должна вывести « \(! \, k \, v_1 \, v_2 \, \ldots \, v_k\) », где \(1 \leq k, v_i \leq n\), все \(v_i\) различны. Этот запрос означает, что банда состоит из \(k\) преступников, которые живут около перекрёстков \(v_1, v_2, \ldots, v_k\). На этом текущее решение задачи поиска местоположений преступников заканчивается и будет снова введен символ.
Гарантируется, что вашей программе нужно будет не менее \(1\) и не более \(10\) раз решать задачу поиска местоположения преступников. В каждой из таких задач количество преступников в банде будет не менее \(1\) и не более \(10\). Также гарантируется, что для местоположений преступников будут выполнены все условия, описанные в условии задачи. В ходе каждого решения задачи поиска местоположений преступников, ваша программа может сделать не более \(100\) запросов слежки за множеством перекрёстков.
После каждого действия вашей программы выводите перевод строки. После каждого действия вашей программы делайте сброс потока вывода.
Если вы используете « writeln » в Паскале, « cout « ... « endl » в C++, « System.out.println » в Java, « print » в Python, « Console.WriteLine » в C#, то сброс потока вывода у вас происходит автоматически, дополнительно ничего делать не требуется. Если вы используете другой способ вывода, рекомендуется делать сброс потока вывода. Обратите внимание, что перевод строки надо выводить в любом случае.
| Группа | Баллы | Дополнительные ограничения | Необх. группы | Комментарий |
| 0 | 0 | – | – | Тесты из условия. |
| 1 | 13 | есть ровно \(1\) преступник | – | |
| 2 | 14 | дерево представляет один путь, состоящий из \(n-1\) улицы | – | |
| 3 | 15 | все улицы соединяют перекрёсток \(1\) с каким-то другим, все преступники живут у перекрёстков с номерами, не меньшими, чем 2 | – | |
| 4 | 11 | из каждого перекрёстка, около которого живет преступник выходит не более одной улицы | 3 | |
| 5 | 21 | \(n \leq 100\) | 0 | |
| 6 | 26 | – | 0–5 |
5 1 2 2 3 3 4 3 5 3 1 3 2 1 5 3 4 5 2
3 4 8 10