给定一个包含 $n$ 个顶点的连通平面图。起初，你位于顶点 $1$。之后，每一秒你都会移动到当前顶点的一个相邻顶点：目标顶点是从所有相邻顶点中等概率随机选择的。你的任务是计算首次到达顶点 $n$ 所需时间的期望值。

输入格式

第一行包含一个整数 $n$：给定平面图的顶点数 ($2 \le n \le 3000$)。 接下来的 $n$ 行包含顶点所在坐标的描述。第 $i$ 行包含两个整数 $x_i$ 和 $y_i$ ($0 \le x_i, y_i \le 5000$)。保证所有给定的点互不相同。 下一行包含一个整数 $m$：给定平面图的边数 ($n-1 \le m \le \frac{n(n-1)}{2}$)。 接下来的 $m$ 行描述图的边。第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$)。这意味着顶点 $a_i$ 和 $b_i$ 之间存在一条边，该边为连接对应点的线段。保证给定的线段中没有两条线段相交（它们只能在公共端点处相交），没有重边，且图是连通的。

输出格式

题目保证在给定的测试中，所需的期望值可以表示为不可约分数 $\frac{P}{Q}$，其中 $P, Q > 0$。你需要输出 $(P \cdot Q^{-1}) \pmod{998\,244\,353}$ 的值。

样例

样例输入 1

2
0 0
35 35
1
1 2

样例输出 1

1

样例输入 2

6
0 0
1 1
2 4
3 9
4 16
5 25
8
1 2
2 3
2 4
3 4
4 5
5 6
1 6
2 6

样例输出 2

798595486