Problem F
Galactic Warlords
Will the galaxy see peace at last? All the warlords have gathered to divide all of space between themselves. The negotiations have come quite far and the warlords have finally agreed on a peaceful way of deciding who gets what. The $2$-dimensional galactic map must first be divided into sectors by splitting it along a set of infinite lines. The warlord with the largest battle fleet will choose one sector, then the warlord with the second largest fleet will choose some other sector and so on, until everyone has gotten a sector. This is then repeated until there are no sectors left.
Different sets of lines have been suggested, and it is up to you to present these alternatives to the meeting. To make sure that there will be peace, you are ready to modify the suggestions slightly. You have some experience with warlords and know that no warlord will settle for less space than anyone else, so for there to be peace, all of them must get the exact same area on the map. Since space is infinite, so is the map. Some sectors therefore have infinite area, so that is the amount of space everyone wants. How many extra lines do you have to add to make sure each warlord can get at least one sector with infinite area?
Input
The first line of input contains two positive integers $W$ and $N$, ($1 \leq W,N \leq 100$) denoting the number of warlords and the number of lines in the suggested division of space. This is followed by $N$ lines each containing four integers $x_1$, $y_1$, $x_2$ and $y_2$, each with an absolute value no higher than $10\, 000$. This means that one line is intersecting the two points $(x_1,y_1)$ and $(x_2,y_2)$ on the galactic map. These two points are not be the same.
Output
Output the number of lines you have to add to this suggestion to satisfy all warlords.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 1 1 1 -2 0 |
0 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 3 0 5 5 5 0 0 1 1 2 2 3 3 |
1 |
