OI Problems

## #d6uqz2. Perfect Matchings

$n\leq 2000$

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

2
1 2
1 3
3 4

1

3
1 2
2 3
3 4
4 5
5 6

5