Задача T. Задача Штейнера (приближение) ≡

Условие

На плоскости задано N точек. Требуется соединить их сетью, состоящей из отрезков. Конечной точкой каждого отрезка может служить как любая из заданных точек, так и любая из M дополнительных точек, указанных вашей программой.

Найденная программой сеть не должна быть минимальной из всех возможных описанных сетей. Тест считается пройденным, если сеть, найденная участником, не более чем на 1% длиннее сети, найденной жюри.

Формат входного файла

В начале входного файла содержится число N. За ним следует N пар вещественных чисел x_i y_i - координаты точек.

Формат выходного файла

В начале выходного файла должно содержаться число дополнительных точек M, за которым должны следовать M пар вещественных чисел a_i b_i — координаты точек.

Далее выведите N + M − 1 пару целых чисел от 1 до N + M — описание отрезков. То есть, дополнительным вершинам присваиваются номера от N + 1 до N + M в том порядке, в котором они выведены участником.

Ограничения

1 ≤ N ≤ 50

1 ≤ M ≤ 50

 − 10⁴ ≤ x_i, y_i, a_i, b_i ≤ 10⁴

Примеры тестов

3
0 0
1 0
0 1

1
0.2 0.2
1 4
2 4
4 3