Codeforces Round 549 (Div. 1) |
---|
Закончено |
Это интерактивная задача.
Учёные находятся всего в нескольких шагах от открытия новой оптимизации алгоритма Флойда, позволяющей ему работать за линейное время! Осталась лишь одна часть.
Как известно, для запуска алгоритма Флойда в графе на $$$n$$$ вершинах должно быть по одному ребру между любыми двумя вершинами. У ученых есть такой граф, однако, они ориентировали каждое ребро, то есть направили его ровно в одну из двух сторон.
Для оптимизации Флойда выбраны $$$m$$$ рёбер и покрашены в розовый цвет, остальные ребра покрашены в зеленый. Вы знаете направление каждого из этих $$$m$$$ ребер, однако, направление зеленых рёбер вам заранее неизвестно. За один запрос вы можете узнать направление одного зеленого ребра, но всего вы можете сделать не более $$$2 \cdot n$$$ запросов.
Вам нужно найти такую вершину, от которой любая другая вершина достижима по пути, состоящем из ребер одного цвета. Обратите внимание, ученые могут лукавить, что уже определили направления для всех ребер, и выдавать ответы в зависимости от ваших запросов.
В первой строке находятся два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 100\,000$$$, $$$0 \le m \le 100\,000$$$) — число вершин и число рёбер розового цвета.
В $$$i$$$-й из следующих $$$m$$$ строках находятся два целых числа $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$) — начало $$$i$$$-го ребра розового цвета и его конец. Гарантируется, что все неупорядоченные пары $$$(u_i, v_i)$$$ различны.
Когда вы найдете ответ, выведите «!» и номер вершины, от которой каждая другая достижима по одноцветному пути.
Чтобы узнать направление зеленого ребра между вершинами $$$a$$$ и $$$b$$$, в одной строке через пробел выведите символ «?», а затем два целых числа $$$a$$$ и $$$b$$$.
В ответ на это считайте целое число, которое будет равно $$$1$$$, если ребро направленно от $$$a$$$ к $$$b$$$, и $$$0$$$, если ребро направлено от $$$b$$$ к $$$a$$$.
Вы можете задать не более $$$2 \cdot n$$$ вопросов, в противном случае вы получите вердикт Wrong Answer.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
Ответ $$$-1$$$ вместо $$$0$$$ или $$$1$$$ означает, что ваша программа сделала некорректный запрос или превысила число запросов. Ваша программа должна немедленно завершиться после прочтения ответа $$$-1$$$, вы получите вердикт Неправильный ответ. В противном случае вы можете получить любой вердикт, так как программа продолжит чтение из закрытого потока.
Взломы
Для взлома задайте тест в следующем формате. В первой строке должны находиться два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 300$$$, $$$0 \le m \le n \cdot (n - 1) / 2$$$) — число вершин и число рёбер розового цвета.
В $$$i$$$-й из следующих $$$m$$$ строк должны находиться два целых чисел $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \ne b_i$$$)), означающих, что есть ребро розового цвета от вершины $$$a_i$$$ к вершине $$$b_i$$$. Все неориентированные пары $$$(a_i, b_i)$$$ должны быть различны.
В $$$i$$$-й из следующих $$$(n \cdot (n - 1) / 2 - m)$$$ строках должны находиться два целых числа $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \ne b_i$$$)), означающих, что есть ребро зеленого цвета от вершины $$$a_i$$$ к вершине $$$b_i$$$. Все неориентированные пары $$$(a_i, b_i)$$$ должны быть различны и не должны совпадать с теми же парами для рёбер розового цвета.
4 2 1 2 3 4 0 1 1
? 1 3 ? 4 2 ? 3 2 ! 3
В приведённом примере ответ на запрос «? 1 3» — 0, поэтому ребро ориентированно от 3 к 1; ответ на запрос «? 4 2» — 1, поэтому ребро ориентированно от 4 к 2; ответ на запрос «? 3 2» — 1, поэтому ребро ориентированно от 3 к 2. Тогда от вершины 3 есть пути по зелёным рёбрам к вершинам 1 и 2, а так же есть путь по розовым рёбрам до вершины 4.
Название |
---|