Problem Description
Rar the Cat has a list of N dots on a piece of paper. He asked K other cats to draw lines on the piece of paper such that each cat will connect all the dots once. The cats are known to draw the shortest total distance of lines to achieve their objective (connect all the dots). However, a cat cannot draw another line between a point A and point B directly if a line has been already drawn between point A and point B by a previous cat (or itself). (Each cat must connect all the dots without drawing over another cat's lines in successive order and each cat will always minimize the total distance it draws during its turn.)
Your task is to find the largest number of cats (maximum K) that Rar the Cat can ask to draw in successive order.
Input
The first line of input consists of a single integer, N.
The following N lines consists of 2 integers each: X followed by Y. They are the X and Y co-ordinates of the point. There will be a total of N points described by N lines. X and Y will both have a difference of not more than 1million from 0.
Output
Output the maximum K, the maximum number of other cats Rar the Cat can ask.
Limits
Subtask 1 (10%): 0 < N ≤ 10
Subtask 2 (21%): 0 < N ≤ 100
Subtask 3 (22%): 0 < N ≤ 500
Subtask 4 (47%): 0 < N ≤ 1000
Subtask 5 (0%): As per Sample Testcases.
Sample Testcase 1
Input:
4
0 0
0 2
2 0
1 1
Output:
1
Explanation:
Rar the Cat can ask one cat to draw, and the first cat will draw lines between (0, 0) to (1, 1), (0, 2) to (1, 1), (2, 0) to (1, 1). This will
However, Rar the Cat cannot ask another cat to draw as no line can be drawn to the point (1, 1) already.