406112: GYM102268 E Expected Value

You are given a connected plane graph on $$$n$$$ vertices. At first, you are standing at vertex $$$1$$$. Then, each second you are going to some vertex adjacent to the current one: the destination vertex is chosen uniformly at random among all adjacent vertices. Your task is to calculate the expected value of the first time you arrive at vertex $$$n$$$.

The first line of input contains one integer $$$n$$$: the number of vertices in the given plane graph ($$$2 \leq n \leq 3000$$$).

The next $$$n$$$ lines contain the description of the points where vertices are located. The $$$i$$$-th of them contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$0 \leq x_i, y_i \leq 5000$$$). It is guaranteed that all given points are distinct.

The next line of input contains one integer $$$m$$$: the number of edges in the given plane graph ($$$n - 1 \leq m \leq \frac{n \cdot (n - 1)}{2}$$$).

The next $$$m$$$ lines describe edges of the graph. The $$$i$$$-th of these lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \neq b_i$$$). It means that there is an edge between vertices $$$a_i$$$ and $$$b_i$$$ which is the segment between the corresponding points. It is guaranteed that no two of the given segments are intersecting (they can intersect only at the common ends), there are no multiple edges, and the graph is connected.

It is guaranteed that, in the given tests, the required expected value can be represented as an irreducible fraction $$$\frac{P}{Q}$$$ where $$$P, Q > 0$$$. You need to print the value $$$(P \cdot Q^{-1})$$$ modulo $$$998\,244\,353$$$.

2
0 0
35 35
1
1 2

1

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

798595486