[Solution] Counting Shortcuts solution codeforces

Counting Shortcuts solution codeforces – 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 11 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 11. 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).

Counting Shortcuts solution codeforcesGraph consisting of 66 of vertices and 88 of edges

Counting Shortcuts solution codeforces

For example, let 𝑛=6n=6𝑚=8m=8𝑠=6s=6 and 𝑡=1t=1, and let the graph look like the figure above. Then the length of the shortest path from 𝑠s to 𝑡t is 11. Consider all paths whose length is at most 1+1=21+1=2.

  • 616→1. The length of the path is 11.
  • 6416→4→1. Path length is 22.
  • 6216→2→1. Path length is 22.
  • 6516→5→1. Path length is 22.

There is a total of 44 of matching paths.

Input

The first line of test contains the number 𝑡t (1𝑡1041≤t≤104) —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𝑛21052≤n≤2⋅1051𝑚21051≤m≤2⋅105) —the number of vertices and edges in the graph.

Counting Shortcuts solution codeforces

The second line contains two numbers 𝑠s and 𝑡t (1𝑠,𝑡𝑛1≤s,t≤n𝑠𝑡s≠t) —the numbers of the start and end vertices of the path.

The following 𝑚m lines contain descriptions of edges: the 𝑖ith line contains two integers 𝑢𝑖ui𝑣𝑖vi (1𝑢𝑖,𝑣𝑖𝑛1≤ui,vi≤n) — the numbers of vertices that connect the 𝑖ith 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 21052⋅105. Similarly, it is guaranteed that the sum of values 𝑚m on all test cases of input data does not exceed 21052⋅105.

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

Since this number may be too large, output it modulo 109+7109+7.

Example
input

Copy

Counting Shortcuts solution codeforces

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

Copy
2
4
1
11

For Solution

Click Here

Leave a Comment