걸어서 트리 속으로

시사 교양 프로그램 '걸어서 트리 속으로'의 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 \leq i < N$)
• 각 나라에서 모든 나라로 비행기를 통해 이동할 수 있다.