기대값

정점이 $n$개인 연결된 평면 그래프가 주어진다. 처음에 정점 1에 서 있다. 매 초마다 현재 정점과 인접한 정점 중 하나를 균등한 확률로 골라 이동한다. 정점 $n$에 처음 도착하는 시각의 기댓값을 구하라.

첫 줄에 정점의 수 $n$이 주어진다 ($2 \le n \le 3000$). 이어지는 $n$개의 줄에는 각 정점의 좌표 $x_i$, $y_i$가 주어진다 ($0 \le x_i, y_i \le 5000$). 모든 점은 서로 다르다.

다음 줄에는 간선의 수 $m$이 주어진다 ($n - 1 \le m \le n(n-1)/2$). 이어지는 $m$개의 줄에는 정점 $a_i$와 $b_i$를 잇는 간선이 주어지며, 간선은 두 점을 잇는 직선 선분이다 ($1 \le a_i, b_i \le n$, $a_i \ne b_i$). 서로 다른 선분은 공통 끝점을 제외하고 교차하지 않으며, 다중 간선은 없고, 그래프는 연결되어 있다.

주어진 테스트에서 기댓값은 기약분수 $P/Q$ ($P, Q > 0$)로 나타낼 수 있다고 보장된다. $P \times Q^{-1}$을 998244353으로 나눈 나머지를 출력하라.