|
Темы:
Топологическая сортировка
Сегодня у Кэрол выходной. Но даже в этот прекрасный весенний день она не отдыхает, а тренируется и готовится к сражениям со скруллами. Одним из важных навыков является умение быстро ориентироваться в незнакомых местах. Для того, чтобы отточить это умение, Кэрол пригласила своего наставника Йон-Рогга.
Кэрол и Йон-Рогг будут играть в следующую игру. Сначала Йон-Рогг нарисует на бумаге карту убежища скруллов. Карта представляет из себя n помещений, пронумерованных от 1 до n. Некоторые пары помещений соединены двусторонними переходами. Убежище устроено так, что от любого помещения до любого другого можно добраться, перемещаясь по коридорам. Для того, чтобы игра не была слишком сложной, Йон-Рогг нарисует ровно n − 1 переход между помещениями. Иными словами, карта убежища представляет собой дерево.
Известно, что для перевозки грузов между помещениями в убежище скруллы используют специальных роботов. Роботы довольно примитивны и плохо ориентируются в убежище. Для решения этой проблемы скруллы выбрали в каждом переходе ровно одно направление, вдоль которого могут перемещаться роботы.
После того, как Йон-Рогг нарисует на бумаге карту убежища, он также для каждого перехода отметит, в каком направлении по нему перемещаются роботы. Иными словами, Йон-Рогг ориентирует ребра нарисованного дерева.
Чтобы структурировать карту убежища, Кэрол должна составить список, состоящий из всех номеров помещений в некотором порядке. При этом должно выполняться следующее условие: в любом переходе роботы перемещаются от помещения, которое идет в списке раньше, к помещению, которое идет с писке позже. Более формально, Кэрол должна составить такую перестановку номеров помещений p1p2 . . . pn, для которой верно, что если роботы могут перемещаться по переходу от помещения pi к помещению pj , то i < j.
Пока Кэрол бьется над своим заданием, Йон-Роггу стало интересно, сколько всего решений существует у этой задачи. Иными словами, Йон-Роггу интересно, сколько перестановок удовлетворяют условию, описанному выше. Помогите ему узнать это. Так как ответ может быть очень большим, Йон-Рогг попросил вас сообщить лишь его остаток от деления на 998 244 353.
Входные данные: Первая строка входных данных содержит единственное целое число n — количество помещений в убежище, нарисованном Йон-Роггом (1 <= n <= 3 000).
Каждая из следующих n − 1 строк содержит два целых числа a, b — номера помещений, соединенных очередным коридором (1 <= a, b <= n). Роботы перемещаются по коридору в направлении от помещения a к помещению b.
Гарантируется, что убежище представляет собой дерево, то есть от любого помещения можно добраться до любого другого, двигаясь по переходам (возможно, в направлении, противоположном направлению движения роботов в этом переходе).
Выходные данные: Выведите остаток от деления на 998 244 353 количества различных перестановок p1p2 . . . pn, для которых верно, что если роботы перемещаются по переходу от помещения pi к помещению pj , то i < j.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3
1 2
1 3
|
2 |
| 2 |
4
2 3
3 1
2 4
|
3 |
Замечание
В первом тесте из примера Кэрол может выписать две перестановки: {1, 2, 3} или {1, 3, 2}.
Во втором тесте Кэрол может выписать три перестановки: {2, 3, 1, 4}, {2, 3, 4, 1} или {2, 4, 3, 1}.
|