Ограничение времени | 1 секунда |
Ограничение памяти | 256 Мб |
Ввод | стандартный ввод |
Вывод | стандартный вывод |
В этой задаче на проверку необходимо сдать исходный код программы.
Мурмурградск — город котиков! И, как и во всех таких городах, в Мурмурградске у каждого котика есть собственный дом, а у каждого домика — уникальный номер. Котики не любят мочить лапки, поэтому некоторые дома соединены специальными котодорожками, полностью защищенными от воды.
Многолетние исследования показали следующие примечательные черты Мурмурградска:
1. Дома и котодорожки представляют собой дерево, где дома — вершины, а котодорожки — ребра.
2. Между двумя домами есть котодорожка тогда и только тогда, когда котики в этих домах дружат.
Кошачий мэр решил, что для развития общей сплоченности каким-то котикам нужно будет поменять место жительства. При этом мэру важно, чтобы у всех оставалось свое личное пространство, поэтому никакие два котика не должны жить в одном доме после переезда. Мэр также понял, что, во избежание всеобщего хаоса, надо добавить в план немного стабильности: жители домика номер должны остаться на месте.
Но и у котиков тоже есть свои требования, так как они не любят сильно менять обстановку. Им крайне важно, чтобы после переселения в другой домик они смогли добраться до всех своих друзей, пройдя не более чем одну котодорожку.
У мэра слишком много дел, поэтому за помощью он обратился к вам! Он поставил перед вами следующую задачу: посчитать, сколько существует планов переезда, удовлетворяющих и критериям мэра, и критериям населения.
Так как это число может быть очень большим, необходимо посчитать его по модулю .
В первой строке записано одно целое число — количество наборов входных данных. Далее следуют наборов входных данных.
Каждый набор данных состоит из нескольких строк. Первая строка набора данных содержит одно целое число — количество вершин в дереве. Далее идут строк, каждая содержит два целых числа и ( , ) — две вершины, которые соединены ребром.
Гарантируется, что заданный граф является деревом, в нем отсутствуют петли и кратные ребра.
Для каждого набора входных данных выведите в отдельной строке одно целое число — количество подходящих планов переезда по модулю .
Оценка за эту задачу — баллов, тестирование проводится онлайн (после тура баллы за задачу не изменятся).
За каждый тест, для которого был найден правильный ответ, начисляется балл.
Тесты | Дополнительные ограничения | |||
---|---|---|---|---|
2-4 | дополнительно | |||
— | ||||
Количество подходящих планов переезда не превосходит | ||||
Количество подходящих планов переезда не превосходит |
Ввод | Вывод |
---|---|
1 6 5 2 1 3 5 4 1 5 1 6 | 4 |