Афанасий – автор детских раскрасок. Недавно он решил, что изготовлять раскраски будет по совершенно новой технологии. А именно, изначально он отмечает на листе бумаги n точек, и соединяет эти точки отрезками так, чтобы никакие два отрезка не пересекались и из каждой точки выходило не более трех отрезков. В результате лист бумаги распадается на фигуры. Дети раскрашивают каждую образовавшуюся фигуру в уникальный цвет. Раскраска считается тем лучше, чем больше цветов потребуется детям, чтобы ее раскрасить. Помогите Афанасию выбрать такое расположение n точек и отрезков между ними, чтобы количество цветов было максимально.
По заданному числу n выведите такой плоский граф, что:
в нём n вершин,
степень каждой вершины не превышает трех,
число граней максимально.
Одно натуральное число n, 1 ≤ n ≤ 1000.
В первых n строках выведите по два целых числа ai, bi (|ai| ≤ 109, |bi| ≤ 109), разделенных пробелом. В i-ой строке – координаты i-ой вершины графа (1 ≤ i ≤ n). Никакие две пары координат не должны совпадать.
В следующей строке выведите целое число m (0 ≤ m ≤ 10000) – число ребер графа.
В следующих m строках выведите по два натуральных числа ui, vi (1 ≤ ui, vi ≤ n, ui ≠ vi), разделенных пробелом, которые задают отрезок, соединяющий вершины ui и vi. Каждый отрезок должен быть упомянут ровно один раз. Из каждой точки должно выходить не более трех отрезков, любые два различных отрезка не должны иметь общих точек, кроме своих концов.
2
-1000000000 -1000000000
1000000000 1000000000
0
7
0 0
4 0
0 2
4 2
1 1
3 1
2 1
10
1 2
1 3
1 5
2 4
2 6
3 4
3 5
4 6
5 7
6 7
