Image by Finn Lidbetter, CC BYSA 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 \neq 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.
Input
The input consists of a single test case. The first line
contains two spaceseparated integers $N, M$, the number of dots in the
picture, and the number of line segments to be drawn,
respectively, with $1\leq N\leq
1\, 000$, $0\leq M\leq 3\,
000$. Each of the next $N$ lines gives the the $x$ and $y$coordinates of one dot as
$2$ spaceseparated
integers $x, y$. It is
guaranteed that $10\, 000\leq
x,y\leq 10\, 000$. These $N$ lines correspond to dots with
indices $0, 1, 2, \ldots ,
N1$ in the order given. All $N$ dots are at distinct locations.
Each of the next $M$ lines
contains $2$
spaceseparated 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\leq j,k\leq N1$ and $j\neq 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.
Sample Input 1 
Sample Output 1 
4 4
0 0
4 0
4 3
6 5
0 1
1 2
0 2
3 2

2

Sample Input 2 
Sample Output 2 
4 3
1 0
1 0
0 1
0 1
0 1
2 3
0 2

1

Sample Input 3 
Sample Output 3 
4 2
0 0
1 0
2 0
3 0
0 1
2 3

1
