Walking Through the Tree

Jong-gyeong, the PD of the current affairs and culture program 'Walking Through the Tree', wants to film each of $N$ countries exactly once. The countries are numbered from 1 to $N$. There are $N-1$ two-way direct flights connecting pairs of countries, and every country can reach every other country by plane. When moving from one country to another, you may only use flights, and you must move so that the number of flights taken is minimized.

Jong-gyeong wants to choose the filming order carefully to raise ratings. For this, the order $A[0] \rightarrow A[1] \rightarrow \cdots \rightarrow A[N-1]$ of the $N$ countries must additionally satisfy the following condition.

• For every $i$ with $0 \le i < N$, $\text{dist}(A[i], A[i+1]) + \text{dist}(A[i+1], A[i+2]) \neq \text{dist}(A[i], A[i+2])$ (where $A[N] = A[0]$ and $A[N+1] = A[1]$)

Here, $\text{dist}(x, y)$ is the minimum number of flights needed to travel from country $x$ to country $y$.

Find the number of valid orders of the countries, modulo $998\,244\,353$.

The first line contains the number of countries $N$.

From the second line through the $N$-th line, the $(i+1)$-th line contains two integers $x_i$ and $y_i$ separated by a space. This means the $i$-th flight is a two-way direct flight connecting country $x_i$ and country $y_i$.

Print the answer on the first line.

• $3 \leq N \leq 300$
• $1 \leq x_i, y_i \leq N$ ($1 \leq i < N$)
• Every country can reach every other country by plane.