402946: GYM100957 A Раскраска

A. Раскраскаограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Афанасий – автор детских раскрасок. Недавно он решил, что изготовлять раскраски будет по совершенно новой технологии. А именно, изначально он отмечает на листе бумаги n точек, и соединяет эти точки отрезками так, чтобы никакие два отрезка не пересекались и из каждой точки выходило не более трех отрезков. В результате лист бумаги распадается на фигуры. Дети раскрашивают каждую образовавшуюся фигуру в уникальный цвет. Раскраска считается тем лучше, чем больше цветов потребуется детям, чтобы ее раскрасить. Помогите Афанасию выбрать такое расположение n точек и отрезков между ними, чтобы количество цветов было максимально.

По заданному числу n выведите такой плоский граф, что:

в нём n вершин,

степень каждой вершины не превышает трех,

число граней максимально.

Входные данные

Одно натуральное число n, 1 ≤ n ≤ 1000.

Выходные данные

В первых n строках выведите по два целых числа a_i, b_i (|a_i| ≤ 10⁹,  |b_i| ≤ 10⁹), разделенных пробелом. В i-ой строке – координаты i-ой вершины графа (1 ≤ i ≤ n). Никакие две пары координат не должны совпадать.

В следующей строке выведите целое число m (0 ≤ m ≤ 10000) – число ребер графа.

В следующих m строках выведите по два натуральных числа u_i, v_i (1 ≤ u_i,  v_i ≤ n,  u_i ≠ v_i), разделенных пробелом, которые задают отрезок, соединяющий вершины u_i и v_i. Каждый отрезок должен быть упомянут ровно один раз. Из каждой точки должно выходить не более трех отрезков, любые два различных отрезка не должны иметь общих точек, кроме своих концов.

ПримерыВходные данные

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