Задача №111783. Музей

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

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

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).

Примеры
Входные данные
6 1000
1 2
2 3
3 1
3 4
4 5
4 6
Выходные данные
20
Сдать: для сдачи задач необходимо войти в систему