Building buildings all day is so boring, so XadillaX organized a race in Minecraft.

To increase the difficulty and fun, XadillaX build some walls on the racing ground. The racing ground is a rectangle and all the walls are on the ground with negligible thick. That means the thick of the wall can be ignored. So on the small map, it look like that:

In fact, everyone's speed in Minecraft is the same. We assume that the ground is N * N miles, there're W walls and the speed of each player is 1 mile per second. The starting point is (0, 0) and the destination is (N, N).
Hungar gets the small map, so he can cheat! But he's too stupid to cheat. Can you help Hungar to calculate out the minimum time that Hungar can get to the destination from the starting point?

This problem contains several cases.
The first line of each case are two numbers, N and W. N indicates the side length of the city and W 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 second that Hungar can get to the destination, two decimal places.