걸어서 트리속으로

시사 교양 프로그램 '걸어서 트리속으로'의 PD인 종경이는 $N$개의 나라를 한 번씩 촬영하려고 한다. 각 나라의 번호는 $1$번부터 $N$번까지이다. 두 나라를 잇는 $N-1$개의 양방향 직항 항공편이 있으며, 각 나라에서 모든 나라로 비행기를 통해 이동할 수 있다. 한 나라에서 다른 나라로 이동할 때는 비행기만 이용해야 하며, 비행기 탑승 횟수를 최소화하는 방법으로 이동해야 한다.

종경이는 촬영 순서를 잘 정하여 시청률을 높이고자 한다. 이를 위해 $N$개 나라의 순서 $A\[0]\rightarrow A\[1]\rightarrow \cdots \rightarrow A\[N-1]$는 다음 조건을 추가로 충족해야 한다.

• $0 \le i < N$인 모든 $i$에 대해, $\text{dist} (A\[i], A\[i+1]) + \text{dist} (A\[i+1], A\[i+2]) \neq \text{dist} (A\[i], A\[i+2])$ (단, $A\[N] = A\[0], A\[N+1] = A\[1]$)

단, $\text{dist} (x, y)$는 $x$번 나라에서 $y$번 나라로 이동할 때, 비행기에 탑승하는 최소 횟수를 나타낸다.

바쁜 종경이를 대신하여, 나라들의 순서를 정하는 방법의 수를 $998\\,244\\,353$으로 나눈 나머지를 구해주자.

첫 줄에 나라의 개수 $N$이 주어진다.

두 번째 줄부터 $N$번째 줄까지 $i+1$번째 줄에는 두 정수 $x\_i$, $y\_i$가 공백을 사이에 두고 주어진다. 이는 $i$번째 항공편이 $x\_i$번과 $y\_i$번 나라를 연결하는 양방향 직항편이라는 것을 의미한다.

첫 번째 줄에 구한 답을 출력한다.

• $3\leq N\leq 300$
• $1\leq x\_i, y\_i \leq N$ ($1 \le i < N$)
• 각 나라에서 모든 나라로 비행기를 통해 이동할 수 있다.