Module: Topologische Sortierung

Carol hat heute einen freien Tag. Aber selbst an diesem schönen Frühlingstag ruht sie sich nicht aus, sondern trainiert und bereitet sich auf die Kämpfe mit den Skrulls vor. Eine wichtige Fähigkeit ist die Fähigkeit, sich schnell an unbekannten Orten zu orientieren. Um diese Fähigkeit zu verbessern, lud Carol ihren Mentor Jon-Rogg ein.

Carol und Jon-Rogg werden das nächste Spiel spielen. Zuerst wird Jon-Rogg eine Karte von Scrulls Zuflucht auf Papier zeichnen. Die Karte besteht aus n Räumen, die von 1 bis n nummeriert sind. Einige Raumpaare sind durch Zweiwegübergänge verbunden. Die Zuflucht ist so eingerichtet, dass Sie von jedem Raum aus durch Flure zu jedem anderen gelangen können. Um sicherzustellen, dass das Spiel nicht zu kompliziert ist, wird Jon-Rogg genau n − 1 den Übergang zwischen den Räumen zeichnen. Mit anderen Worten: Die Zufluchtskarte ist ein Baum.

Es ist bekannt, dass Skrulles spezielle Roboter verwenden, um Güter zwischen den Unterkünften zu transportieren. Roboter sind ziemlich primitiv und orientieren sich nicht gut im Versteck. Um dieses Problem zu lösen, haben die Scrolls in jedem Übergang genau eine Richtung gewählt, an der sich Roboter bewegen können.

Nachdem Jon-Rogg eine Zufluchtskarte auf Papier gezeichnet hat, wird er auch für jeden Übergang feststellen, in welche Richtung sich die Roboter bewegen. Mit anderen Worten, Jon-Rogg orientiert die Kanten des gezeichneten Baumes.

Um die Asylkarte zu strukturieren, muss Carol eine Liste erstellen, die aus allen Zimmernummern in einer bestimmten Reihenfolge besteht. Dabei muss die folgende Bedingung erfüllt sein: Bei jedem Übergang bewegen sich die Roboter von einem Raum, der früher in der Liste steht, zu einem Raum, der später mit der Pike geht. Formal muss Carol eine solche Umordnung der Zimmer  machen;der Räume p₁p₂ . . . p_n, für die es wahr ist, dass, wenn Roboter den Übergang von Raum pi zu Raum p_j bewegen können , dann i < j.

Während Carol über ihre Aufgabe kämpft, hat sich Jon-Rogg gefragt, wie viele Lösungen es für diese Aufgabe gibt. Mit anderen Worten, Jon-Roggu fragt sich, wie viele Permutationen die oben beschriebene Bedingung erfüllen. Hilf ihm, das herauszufinden. Da die Antwort sehr groß sein kann,hat Sie Yon-Rogg gebeten, nur seinen Rest von der Division durch 998 244 353 mitzuteilen.

Eingabe: Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl n — Anzahl der Räume in einem von Yon Rogg gezeichneten Versteck (1 <= n <= 3 000).

Jede der folgenden n − 1 Zeilen enthält zwei ganze Zahlen a, b — Raumnummern, die durch einen weiteren Korridor verbunden sind (1 <= a, b <= n). Die Roboter bewegen sich durch den Korridor in der Richtung von Raum a nach Raum b.

Es ist garantiert, dass es sich bei der Zuflucht um einen Baum handelt, dh von jedem Raum aus kann man durch Bewegen der Übergänge zu jedem anderen gelangen (möglicherweise in die entgegengesetzte Richtung der Bewegungsrichtung der Roboter in diesem Übergang).

Ausgabe Daten: Geben Sie den Rest der Division durch 998 244 353 Anzahl der verschiedenen Permutationen aus p₁p₂ . . . p_n, für die es wahr ist, dass Roboter, wenn sie sich vom Raum p_i zum Raum p_j bewegen, i < j.
 

Im ersten Test aus dem Beispiel kann Carol zwei Permutationen schreiben: {1, 2, 3} oder {1, 3, 2}.

Im zweiten Test kann Carol drei Permutationen schreiben: {2, 3, 1, 4}, {2, 3, 4, 1} oder {2, 4, 3, 1}.