Shortest Path

There is a path graph $G=(V,E)$ with $n$ vertices. Vertices are numbered from $1$ to $n$ and there is an edge with unit length between $i$ and $i + 1$ $(1 \le i < n)$. To make the graph more interesting, someone adds three more edges to the graph. The length of each new edge is $1$.

You are given the graph and several queries about the shortest path between some pairs of vertices.

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains two integer $n$ and $m$ $(1 \le n, m \le 10^5)$ -- the number of vertices and the number of queries. The next line contains 6 integers $a_1, b_1, a_2, b_2, a_3, b_3$ $(1 \le a_1,a_2,a_3,b_1,b_2,b_3 \le n)$, separated by a space, denoting the new added three edges are $(a_1,b_1)$, $(a_2,b_2)$, $(a_3,b_3)$.

In the next $m$ lines, each contains two integers $s_i$ and $t_i$ $(1 \le s_i, t_i \le n)$, denoting a query.

The sum of values of $m$ in all test cases doesn't exceed $10^6$.

For each test cases, output an integer $S=(\displaystyle\sum_{i=1}^{m} i \cdot z_i) \text{ mod } (10^9 + 7)$, where $z_i$ is the answer for $i$-th query.

1
10 2
2 4 5 7 8 10
1 5
3 1

7

BestCoder Round #74 (div.2)