Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Walk Less

By kazi_nayeem · Limits 1s, 512 MB

You live in a city which consists of N points. The points are numbered from 1 to n. The distance between any two points u and v is |u-v|. Currently, you are on point 1 and you have to go to point n. You can always walk from any point to any other point.

There are M trains that go from a point to another point. You can use these trains any number of times. But if you enter in a train, you can't leave it until it reaches its destination.

Now you have to find, what is the minimum amount of distance you need to walk to go from point 1 to point n?

Input

The first line contains an integer TT (0<T500 < T \le 50), number of test cases.

The first line of each test case contains two integers NN (1N50001 \le N \le 5000) and MM (0M1000000 \le M \le 100000) where NN is the number of points and MM is the number of transports. Next MM line contains two integers uu and vv (1u,v N1 \le u, v \le N)where there is a transport that goes from point uu to point vv.

Output

For every test case, print minimum amount of distance you need to walk to go from point 1 to nn.

Sample

InputOutput
3
7 2
1 4
3 7
10 3
2 4
3 6
5 10
5 1
1 5
1
2
0

Discussion

Statistics


54% Solution Ratio

TasdidEarliest, Jan '18

IamHotFastest, 33431.7s

IamHotLightest, 918 kB

Baka_RaffiShortest, 1132B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.