Problem D
Colouring Book

Image by Finn Lidbetter, CC BY-SA 4.0

The Ministry of Trigonometric Artistry (or MTA for short) is producing a colouring book to get children interested in trigonometry at a young age. The colouring book consists of many pages. On each page is a set of numbered dots that are to be connected with straight line segments according to some instructions given on the page. Once these line segments are drawn, the entire page is to be coloured with as many colours as the young trigonometric artist desires, provided that the following rule is obeyed: in order to move continuously from a point anywhere on the page that has been coloured with colour $c_1$ to another point that has been coloured with colour $c_2$, where $c_1\ne c_2$, at least one line segment must be crossed. The dots have zero area, and the line segments have zero thickness (and yet, through the magic of mathematics, they are still visible). Also, none of the dots touch the outer boundary of the page, and the instructions are written in a kind of invisible ink that ensures they do not interfere with the drawing or colouring processes in any way (and yet are still readable).

MTA’s executives would like to determine how fun the colouring book is going to be. So for each picture that the Ministry’s designers have created, the executives want to know the maximum number of colours that can be used to colour that page. They also want to know if the set of instructions that they are giving to join the dots is valid. An instruction set is said to be invalid if (a) there exist two line segments that intersect at a point that is not an endpoint of both of the line segments, (b) there is a dot that lies on a line segment but is not one of its endpoints, or (c) there is a pair of dots that are not connected by some sequence of line segments.

Figure 1: Sample Input #1, coloured with $2$ colours.

Input

The input consists of a single test case. The first line contains two space-separated integers $N,M$, the number of dots in the picture, and the number of line segments to be drawn, respectively, with $1\le N\le 1000$, $0\le M\le 3000$. Each of the next $N$ lines gives the the $x$- and $y$-coordinates of one dot as $2$ space-separated integers $x,y$. It is guaranteed that $-10000\le x,y\le 10000$. These $N$ lines correspond to dots with indices $0,1,2,\dots ,N-1$ in the order given. All $N$ dots are at distinct locations. Each of the next $M$ lines contains $2$ space-separated integers $j$ and $k$ indicating that there is a line segment from the dot with index $j$ to the dot with index $k$, with $0\le j,k\le N-1$ and $j\ne k$. It is guaranteed that there is at most one line segment between any pair of dots.

Output

If the instruction set is invalid, output $-1$. Otherwise, output a single line with an integer $C$, the maximum number of colours that can be used in the picture.

4 4
0 0
4 0
4 3
6 5
0 1
1 2
0 2
3 2

2

4 3
-1 0
1 0
0 1
0 -1
0 1
2 3
0 2

-1

4 2
0 0
1 0
2 0
3 0
0 1
2 3

-1