A14912 | Counting Shortcuts

Given an undirected connected graph with $n$ vertices and $m$ edges. The graph contains no loops (edges from a vertex to itself) and multiple edges (i.e. no more than one edge between each pair of vertices). The vertices of the graph are numbered from $1$ to $n$ .

Find the number of paths from a vertex $s$ to $t$ whose length differs from the shortest path from $s$ to $t$ by no more than $1$ . It is necessary to consider all suitable paths, even if they pass through the same vertex or edge more than once (i.e. they are not simple).

Graph consisting of $6$ of vertices and $8$ of edgesFor example, let $n = 6$ , $m = 8$ , $s = 6$ and $t = 1$ , and let the graph look like the figure above. Then the length of the shortest path from $s$ to $t$ is $1$ . Consider all paths whose length is at most $1 + 1 = 2$ .

- $6 \rightarrow 1$ . The length of the path is $1$ .
- $6 \rightarrow 4 \rightarrow 1$ . Path length is $2$ .
- $6 \rightarrow 2 \rightarrow 1$ . Path length is $2$ .
- $6 \rightarrow 5 \rightarrow 1$ . Path length is $2$ .

There is a total of $4$ of matching paths.

The first line of test contains the number $t$ ( $1 \le t \le 10^4$ ) —the number of test cases in the test.

Before each test case, there is a blank line.

The first line of test case contains two numbers $n, m$ ( $2 \le n \le 2 \cdot 10^5$ , $1 \le m \le 2 \cdot 10^5$ ) —the number of vertices and edges in the graph.

The second line contains two numbers $s$ and $t$ ( $1 \le s, t \le n$ , $s \neq t$ ) —the numbers of the start and end vertices of the path.

The following $m$ lines contain descriptions of edges: the $i$ th line contains two integers $u_i$ , $v_i$ ( $1 \le u_i,v_i \le n$ ) — the numbers of vertices that connect the $i$ th edge. It is guaranteed that the graph is connected and does not contain loops and multiple edges.

It is guaranteed that the sum of values $n$ on all test cases of input data does not exceed $2 \cdot 10^5$ . Similarly, it is guaranteed that the sum of values $m$ on all test cases of input data does not exceed $2 \cdot 10^5$ .

For each test case, output a single number — the number of paths from $s$ to $t$ such that their length differs from the length of the shortest path by no more than $1$ .

Since this number may be too large, output it modulo $10^9 + 7$ .