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.
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 the maximum K, the maximum number of other cats Rar the Cat can ask.
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.
Input:
4 0 0 0 2 2 0 1 1Output:
1Explanation:
| Subtask | Score |
|---|---|
| 1 | 10 |
| 2 | 21 |
| 3 | 22 |
| 4 | 47 |