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 edges

For 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.


-----Input-----

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$.


-----Output-----

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$.


-----Examples-----

Input
4
4 4
1 4
1 2
3 4
2 3
2 4
6 8
6 1
1 4
1 6
1 5
1 2
5 6
4 6
6 3
2 6
5 6
1 3
3 5
5 4
3 1
4 2
2 1
1 4
8 18
5 1
2 1
3 1
4 2
5 2
6 5
7 3
8 4
6 4
8 7
1 4
4 7
1 6
6 7
3 8
8 5
4 5
4 3
8 2
Output
2
4
1
11


-----Note-----

None

Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Shortest paths

Dynamic programming

Data structures
Skill types: Dynamic programming

Data structures

Starter code:

Solutions:
import sys
I = lambda : [*map(int, sys.stdin.readline().split())]
(t,) = I()
for _ in range(t):
	I()
	(n, m) = I()
	(s, t) = I()
	M = 10 ** 9 + 7
	s -= 1
	t -= 1
	g = [[] for i in range(n)]
	for i in range(m):
		(u, v) = I()
		g[u - 1].append(v - 1)
		g[v - 1].append(u - 1)
	distances = [M] * n
	distances[s] = 0
	i = 0
	paths = {s: 1}
	tot = 0
	while i <= distances[t]:
		i += 1
		newpaths = {}
		for v in paths:
			for w in g[v]:
				if distances[w] >= i - 1:
					distances[w] = min(distances[w], i)
					if w in newpaths:
						newpaths[w] = (newpaths[w] + paths[v]) % M
					else:
						newpaths[w] = paths[v]
		paths = newpaths
		if t in paths:
			tot += paths[t]
	print(tot % M)


from collections import deque
mod = 10 ** 9 + 7

def add(a, b):
	return (a % mod + b % mod) % mod

def answer():
	whichlevel = [-1 for i in range(n + 1)]
	whichlevel[s] = 0
	q = deque([s])
	while len(q):
		p = q.popleft()
		for i in adj[p]:
			if whichlevel[i] != -1:
				continue
			whichlevel[i] = whichlevel[p] + 1
			q.append(i)
	dp = [[0, 0] for i in range(n + 1)]
	dp[s][0] = 1
	v = [[False, False] for i in range(n + 1)]
	q = deque([[s, 0]])
	while len(q):
		(p, lvl) = q.popleft()
		parentlvldiff = lvl - whichlevel[p]
		if v[p][parentlvldiff]:
			continue
		v[p][parentlvldiff] = True
		for i in adj[p]:
			if lvl + 1 - whichlevel[i] > 1:
				continue
			childlvldiff = lvl + 1 - whichlevel[i]
			dp[i][childlvldiff] = add(dp[i][childlvldiff], dp[p][parentlvldiff])
			q.append([i, lvl + 1])
	ans = add(dp[t][0], dp[t][1])
	return ans
for T in range(int(input())):
	input().strip()
	(n, m) = map(int, input().split())
	(s, t) = map(int, input().split())
	adj = [[] for i in range(n + 1)]
	for i in range(m):
		(u, v) = map(int, input().split())
		adj[u].append(v)
		adj[v].append(u)
	print(answer())