30096번 - 걸어서 트리속으로

문제

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

힌트