eolymp
Competitions

XXIII Всеукраинская олимпиада по информатике, Киев, Март 22 - 26, 2010

Музей

В столице страны Олимпия построен Музей Олимпийской Славы, в котором выставлены награды школьников страны с разных предметных олимпиад. Здание музея сосотоит из выставочных залов, соединённых коридорами. Коридор соединяет ровно два зала. Известно, что в каждый зал музея можно добраться из любого другого зала, идя по коридорам. Также известно, что количество коридоров равно количеству залов.

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

  1. Для каждого зала план задаёт или остаётся его охранник на месте, или перейдёт в определённый зал, который соединён с текущим коридором.
  2. После переходов охранников, в каждом зале должен оказаться ровно один охранник.
  3. Каждый час применяется один и тот же план патрулирования.

Например, на рисунке приведён один из возможных планов патрулирования. Согласно ему каждый час охранник, находящийся в зале 1, переходит в зал 2; охранник из залв 2 – в зал 3; из зала 3 – в зал 1; охранники из залов 4 и 5 меняются местами, а охранник из зала 6 всю ночь проводит в этом зале.

Напишите программу, которая по информации о количестве залов музею и соединения их коридорами найдёт количество разных планов патрулирования музея по модулю P.

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

Первая строка содержит пару целых чисел N (3 N 50000) - количество залов в музее, и P (2 P 10000). Последующие N строк содержат пары целых чисел от 1 до N - номера залов, соединённых коридором.

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

Вывести одно целое число - количество планов патрулирования музея, по модулю P (остаток от деления искомого количества на P).

Объяснение к примеру: Существует 20 разных планов патрулирования: (1, 2, 3, 4, 5, 6), (1, 2, 3, 5, 4, 6), (1, 2, 3, 6, 5, 4), (1, 2, 4, 3, 5, 6), (1, 3, 2, 4, 5, 6), (1, 3, 2, 5, 4, 6), (1, 3, 2, 6, 5, 4), (2, 1, 3, 4, 5, 6), (2, 1, 3, 5, 4, 6), (2, 1, 3, 6, 5, 4), (2, 1, 4, 3, 5, 6), (2, 3, 1, 4, 5, 6), (2, 3, 1, 5, 4, 6), (2, 3, 1, 6, 5, 4), (3, 1, 2, 4, 5, 6), (3, 1, 2, 5, 4, 6), (3, 1, 2, 6, 5, 4), (3, 2, 1, 4, 5, 6), (3, 2, 1, 5, 4, 6), (3, 2, 1, 6, 5, 4). На рисунке из условия изображён план (2, 3, 1, 5, 4, 6).

Time limit 1 second
Memory limit 256 MiB
Input example #1
6 1000
1 2
2 3
3 1
3 4
4 5
4 6
Output example #1
20
Author Daniil Neiter
Source 2010 XXIII All-Ukrainian Informatics Olympiad, Kiev, March 22 - 26, Round 1