시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 512 MB 5 5 4 100.000%

문제

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 ≤ n ≤ 3000).

The next n lines contain the description of the points where vertices are located. The i-th of them contains two integers xi and yi (0 ≤ xi, yi ≤ 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 ≤ m ≤ n·(n−1)/2).

The next m lines describe edges of the graph. The i-th of these lines contains two integers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi). It means that there is an edge between vertices ai and bi 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 P/Q where P, Q > 0. You need to print the value (P · Q−1) modulo 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

출처

Camp > Petrozavodsk Programming Camp > Winter 2019 > Day 1 E번

  • 문제를 만든 사람: 300iq