One day, after XadillaX waken up, he found that the whole city is strange - everyone become a zombie except him.
So he decided to wait for the helicopter saving him.
This city is a square field that (N * N) square miles, XadillaX is at (0, 0) and helicopter is at (N, N). And there're some high walls block off the helicopter.
The helicopter cannot go through the high walls, but it can go around them.
The helicopter wants to arrive at the point that XadillaX is at as soon as possible.
What are the minimum miles the helicopter should go?

This problem contains several cases.
The first line of each case are two numbers, N and M. N indicates the side length of the city and M is the number of walls. (1.0 <= N <= 100.0, 0 <= M <= 50)
Then follow M lines. Each line has two coordinates x1 y1 x2 y2, indicates the WALLi. You can assume that no two walls are intersected.

For each case, you should print the minimum miles that the helicopter should go, two decimal places.