Страница: 1 Отображать по:
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Телекоммуникационная сеть крупной IT-компании содержит n серверов, пронумерованных от 1 до $n$. Некоторые пары серверов соединены двусторонними каналами связи, всего в сети m каналов. Гарантируется, что сеть серверов устроена таким образом, что по каналам связи можно передавать данные с любого сервера на любой другой сервер, возможно с использованием одного или нескольких промежуточных серверов.

Множество серверов $A$ называется отказоустойчивым, если при недоступности любого канала связи выполнено следующее условие. Для любого не входящего в это множество сервера $X$ существует способ передать данные по остальным каналам на сервер $X$ хотя бы от одного сервера из множества $A$.

На рис. 1 показан пример сети и отказоустойчивого множества из серверов с номерами 1 и 4. Данные на сервер 2 можно передать следующим образом. При недоступности канала между серверами 1 и 2 — с сервера 4, при недоступности канала между серверами 2 и 3 — с сервера 1. На серверы 3 и 5 при недоступности любого канала связи можно по другим каналам передать данные с сервера 4.

В рамках проекта группе разработчиков компании необходимо разместить свои данные в сети. Для повышения доступности данных и устойчивости к авариям разработчики хотят продублировать свои данные, разместив их одновременно на нескольких серверах, образующих отказоустойчивое множество. Чтобы минимизировать издержки, необходимо выбрать минимальное по количеству серверов отказоустойчивое множество. Кроме того, чтобы узнать, насколько гибко устроена сеть, необходимо подсчитать количество способов выбора такого множества, и поскольку это количество способов может быть большим, необходимо найти остаток от деления этого количества способов на число $10^9 + 7$.

Требуется написать программу, которая по заданному описанию сети определяет следующие числа: $k$ — минимальное количество серверов в отказоустойчивом множестве серверов, $c$ — остаток от деления количества способов выбора отказоустойчивого множества из $k$ серверов на число $10^9 + 7$

Входные данные

Первая строка входного файла содержит целые числа $n$ и $m$ — количество серверов и количество каналов связи соответственно ($2 \le n \le 200000$, $1 \le m \le 200000$). Следующие $m$ строк содержат по два целых числа и описывают каналы связи между серверами. Каждый канал связи задается двумя целыми числами: номерами серверов, которые он соединяет.

Гарантируется, что любые два сервера соединены напрямую не более чем одним каналом связи, никакой канал не соединяет сервер сам с собой, и для любой пары серверов существует способ передачи данных с одного из них на другой, возможно с использованием одного или нескольких промежуточных серверов.

Выходные данные

Выведите два целых числа, разделенных пробелом: $k$ — минимальное число серверов в отказоустойчивом множестве серверов, $c$ — количество способов выбора отказоустойчивого множества из $k$ серверов, взятое по модулю $10^9 + 7$

Пояснения к примеру

В приведенном примере отказоустойчивыми являются следующие множества из двух серверов: {1, 3}, {1, 4}, {1, 5}.

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только, если все тесты для этой подзадачи и всех необходимых подзадач успешно пройдены.

Примеры
Входные данные
5 5
1 2
2 3
3 4
3 5
4 5
Выходные данные
2 3
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes

– Это что за остановка – Бологое иль Поповка? – А с платформы говорят: – Это город Ленинград.
«Вот какой рассеянный», Самуил Маршак

Пытаясь спастись от мира спортивного программирования, Алина сбежала на вокзал и уехала прочь на ночной электричке. Минуты медленно уплывали в даль, и уставшую девочку клонило в сон. Ей снился город-сказка, где не надо программировать, а можно гулять, мечтать и наслаждаться жизнью. Внезапно дождь из интерактивных задач разрушил эту идиллию.

Проснувшись и открыв окно, Алина задалась вопросом весьма философского свойства: «Где я?». С перрона потерявшейся девочке сообщили, что этот город, не похожий ни на что вокруг, представляет собой неориентированный граф на $n$ вершинах и $m$ ребрах. Сeй невероятный факт, однако, нисколько не удивил Алину. Она давно мечтала побывать в одном таком городе — Петербурге. Его уникальной отличительной особенностью является то, что хотя бы половина его ребер — мосты (определение дано в конце условия). Так как никакие другие города Алине не интересны, она решила ограничиться расспросом находящихся на платформе эрудированных путешественников. Любой из их них может по данной вершине $v$ сообщить любое ещё не названное ребро, исходящее из нее, или же заявить об отсутствии таковых.

Алина неуверена в своих силах, поэтому попросила вас помочь ей определить, попала ли она в Петербург. Так как её поезд скоро продолжит свой путь, задать больше $3n$ вопросов не получится.

Обратите внимание, что в графе могут присутствовать петли и кратные ребра.

Протокол взаимодействия

В первой строке стандартного потока ввода даны два целых числа $n$ и $m$ ($1 \le n, m \le 100\,000$) — число вершин и ребер в графе соответственно.

Для того, чтобы узнать очередное ребро, исходящее из $u$-й вершины ($1 \le u \le n$), нужно вывести « ? $u$ ». После этого ваша программа на вход получит целое число $v$ ($-2 \le v \le -1$ или $1 \le v \le n$)  — $v = a + b - u$, если существует ребро $ab$, которое инцидентно вершине $u$ и ещё не было названо , $-1$, если такого ребра не существует и $-2$, если вы превысили допустимое число запросов. В последнем случае ваша программа должна немедленно завершиться, в ином случае жюри не гарантирует корректность полученного вами вердикта.

Вам разрешается задать не более $3n$ вопросов.

Чтобы сообщить, что ответ найден, требуется вывести « ! Yes » или « ! No », в зависимости от того, является ли загаданный граф Петербургом. В случае положительного ответа выведите $\lceil\frac{m}{2}\rceil$ строк, по два целых числа $u_i$ и $v_i$ в каждой ($1 \le u_i, v_i \le n$), обозначающих, что ребро $(u_i, v_i)$ является мостом. Любое ребро в приведенном списке должно встречаться не более одного раза (кратные ребра считаются различными).

Запрос на вывод ответа не входит в ограничение на $3n$ запросов.

Не забывайте сбрасывать буфер после каждого запроса. Например, на языке C++ надо использовать функцию fflush(stdout) или вызов cout.flush() , на Java вызов System.out.flush() , на Pascal flush(output) и stdout.flush() для языка Python.

Примечание

В условии в примере взаимодействия вводимые и выводимые данные расположены для удобства восприятия в хронологическом порядке, при реальном взаимодействии никакие «лишние» переводы строк возникать не должны.

Ввод-вывод в примерах демонстрирует пример взаимодействия вашей программы с проверяющей системой.

В первом примере был загадан граф на трех вершинах с ребрами $(1, 2)$, $(2, 3)$ и $(3, 1)$.

Во втором примере была загадан граф на четырех вершинах с ребрами $(1, 2)$, $(2, 3)$, $(3, 4)$ и $(2, 3)$.

Ребро, соединяющее вершины $u$ и $v$, называется мостом, если после его удаления между вершинами $u$ и $v$ не существует пути.

Примеры
Входные данные
3 3

2

2

-1

3

-1

-1
Выходные данные
? 3

? 1

? 2

? 1

? 1

? 3

! No
Входные данные
4 4

2

3

2

-1

4

-1

-1

-1


Выходные данные
? 1

? 2

? 3

? 1

? 3

? 3

? 2

? 4

! Yes
1 2
3 4

Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест