F. Meta Graph
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a connected, undirected, simple graph $$$G$$$ with $$$n$$$ vertices and $$$m$$$ edges, define its meta-graph $$$f(G)$$$ as follows:

  • $$$f(G)$$$ has $$$n^2$$$ vertices, labelled $$$a_b$$$ for $$$1\le a, b\le n$$$.
  • For every edge $$$(a, b)$$$ in $$$G$$$, add the edges $$$(c_a, c_b)$$$ for all $$$1\le c\le n$$$ to $$$f(G)$$$, and also add the edge $$$(a_b, b_a)$$$ to $$$f(G)$$$.

Given two vertices $$$w_x$$$ and $$$y_z$$$, determine the number of edges on the shortest path between them in $$$f(G)$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains the two integers $$$n$$$ and $$$m$$$ ($$$2\le n\le 2\cdot 10^5$$$, $$$n - 1 \le m\le \min\left(2\cdot 10^5, \frac{n(n-1)}{2}\right)$$$) — the number of vertices and the number of edges in $$$G$$$.

The second line contains four integers $$$w$$$, $$$x$$$, $$$y$$$, and $$$z$$$ ($$$1\le w, x, y, z\le n$$$) — the start vertex $$$w_x$$$ and end vertex $$$y_z$$$, respectively.

The next $$$m$$$ lines each contain two integers $$$a$$$ and $$$b$$$ ($$$1\le a \lt b\le n$$$) — the edges of $$$G$$$. It is guaranteed that no edge appears more than once, and that $$$G$$$ is connected.

It is guaranteed that both the sum of $$$n$$$ and the sum of $$$m$$$ over all testcases are bounded by $$$2\cdot 10^5$$$.

Output

For each test case, output a single integer: the number of edges on the shortest path from $$$w_x$$$ to $$$y_z$$$ in $$$f(G)$$$. We can show that at least one path between them always exists under the conditions of the problem.

Example
Input
3
3 2
1 1 3 3
1 2
2 3
4 4
1 1 4 1
1 2
2 3
3 4
1 4
2 1
1 1 1 1
1 2
Output
6
2
0
Note

In the first example, the shortest (and only) path is $$$1_1, 1_2, 2_1, 2_2, 2_3, 3_2, 3_3$$$.

The meta-graph for the first example.

In the second example, the shortest path is $$$1_1, 1_4, 4_1$$$.