Граф на площині#12959

Граф на площині

4 seconds
512 megabytes
Hard

Вам задано різних точок (x_i, y_i) на двовимірній площині.

Неорієнтований зважений граф з дійсними вагами називається хорошим, якщо виконуються такі умови.

Знайдіть мінімальну кількість ребер у хорошому графі.

Input

У першому рядку задано ціле число – кількість точок.

У наступних рядках задано два цілих числа x_i та y_i – координати точок.

1 \le n \le 2000,

|x_i|, |y_i| \le 10^9.

Всі точки різні.

Output

Виведіть одне ціле число – мінімальну кількість ребер у хорошому графі.

Examples

Example

Loading
Loading

Example 1

Loading
Loading

Note

У першому прикладі мінімальна кількість ребер у хорошому графі — шість.

У другому прикладі мінімальна кількість ребер у хорошому графі — вісім.