Олимпиадный тренинг

Задача . Bovine Alliance

Задача

Беси и ее бычок решили соединить свои фермы дорожками, чтобы сформировать союз против фермеров. Коровы в каждой из N (1 <= N <= 100,000) ферм были изначально проинструктированы, чтобы построить одну дорожку ровно к одной другой ферме. Всего получилось N дорожек. Однако через несколько месяцев после начала проекта реально построены были только M (1 <= M < N) дорожек. Беси хочет узнать, сколькими способами могли быть построены эти M дорожек. Например, если между фермами 3 и 4 есть дорожка, Один способ, что ее построила ферма 3, другой - что ферма 4.
Помогите Беси посчитать количество способов назначения к дорожкам построивших их ферм по модулю 1 000 000 007. Два назначения рассматриваются как различные, если хоть одна дорожка построена разными фермами в этих двух назначениях.
PROBLEM NAME: alliance
Формат входных данных
* Строка 1: Два разделенных пробелами целых числа N и M
* Строки 2..1+M: Строка i+1 описывает i-ую дорожку. Каждая строка содержит два разделенных пробелом целых числа u_i v_i (1 <= u_i, v_i <= N, u_i != v_i), описывающих пару ферм, соединенных дорожкой.
Формат выходных данных
* Строка 1: Одна строка, содержащая число назначений дорожек фермам, взятое по модулю 1,000,000,007. Если не существует назначений, удовлетворяющих заданным условиям, выведите 0.
Примечание
Всего существует 6 возможных назначений. Обозначение {a,b,c,d} означает, что ферма 1 построила дорожку a, Ферма 2 построила дорожку b, ферма 3 построила дорожку c, а ферма 4 построила дорожку d. Эти 6 назначений таковы: {2, 3, 4, 5} {2, 3, 5, 4} {1, 3, 4, 5} {1, 3, 5, 4} {1, 2, 4, 5} {1, 2, 5, 4}

Примеры

№	Входные данные	Выходные данные
1	5 4 1 2 3 2 4 5 4 5	6

time 500 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет