L. Perfect Matchings
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

AAA gets a complete graph of $$$2n$$$ vertices, where every pair of distinct vertices is connected by a unique edge, as a birthday present. However, AAA thinks the complete graph is not that beautiful and he decides to delete $$$2n-1$$$ edges that form a tree.

Now he wonders the number of different perfect matchings in the remaining graph. Note that a perfect matching is a set of $$$n$$$ edges where no two edges share a common vertex. Since the answer may be very large, you only need to output the answer modulo $$$998\,244\,353$$$.

Input

The first line contains a single integer $$$n$$$ $$$(2\le n\le 2\,000)$$$.

Each of the next $$$2n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ $$$(1\le u,v\le 2n)$$$, representing an edge deleted from the complete graph. It is guaranteed that the given edges form a tree of $$$2n$$$ vertices.

Output

Output a line containing a single integer, representing the answer modulo $$$998\,244\,353$$$.

Examples
Input
2
1 2
1 3
3 4
Output
1
Input
3
1 2
2 3
3 4
4 5
5 6
Output
5