F. Tipsy Chick
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A group of $$$n$$$ chicks is waiting in a chicken coop. In order to pass the time, they decide to shake each other's wings. They shake wings according to the following rules:

  • Each chick shakes wings with at most one other chick at each distinct round.
  • At the end, for every pair of chicks $$$a$$$ and $$$b$$$, there is a path of wing-shakes that connects $$$a$$$ and $$$b$$$. Note that these wing-shakes do not have to happen in any specific round, but a path that includes wing-shakes over multiple rounds is fine.

They would like to minimize the number of rounds needed. In addition, because their wing aren't fully grown yet, they want to minimize the maximum distance between any two chicks who shake wings (while still minimizing the number of rounds). Output the number of rounds needed, and because they like integers, output the square of the minimum maximum wing-shake distance.

Input

The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 18$$$) — the number of chicks.

The next $$$n$$$ lines contain two space-separated integers $$$x$$$ and $$$y$$$ ($$$1 \leq x, y \leq 10^3$$$) — denoting that there is a chick at location $$$(x, y)$$$. It is guaranteed that all pairs of points are distinct.

Output

On a single line, output two integers — the minimum number of rounds needed and the minimum maximum wing-shake distance needed.

Example
Input
3
1 1
2 2
3 2
Output
2 2
Note

In the sample, it is optimal for chick 1 and chick 2 to shake hands on the first round and chick 2 and chick 3 to shake hands on the second round.