# 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 $T$ ($0 < T \le 50$), number of test cases.

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

## Output

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

## Sample

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

1
2
0


### Statistics

54% Solution Ratio

TasdidEarliest, Jan '18

IamHotFastest, 33431.7s

IamHotLightest, 918 kB

Baka_RaffiShortest, 1132B