Задача . Гигантский дракон

Канеки смотрит на неориентированный граф на плоскости из $n$ вершин и $m$ ребер. В этом графе ему интересно найти самого большого дракона.

Назовем сегментом дракона три ребра графа $AL$, $AB$ и $AR$, имеющие общую вершину $A$, и обладающие следующими свойствами:

• $0 < \measuredangle (BAL) < 45^\circ$ и направление поворота от $\overrightarrow{AB}$ к $\overrightarrow{AL}$ — по часовой стрелке;

• $0 < \measuredangle (BAR) < 45^\circ$ и направление поворота от $\overrightarrow{AB}$ к $\overrightarrow{AR}$ — против часовой стрелки;

• $|AB| \geqslant |AL|$ и $|AB| \geqslant |AR|$, то есть $AB$ — максимальное по длине из трех ребер.

При выполнении всех указанных условий вершины $A$ и $B$ называются началом и концом сегмента, а ребра $AL$, $AB$ и $AR$ — левой лапой, основанием и правой лапой сегмента, соответственно.

Определим дракона как последовательность сегментов, в которой

• начало первого сегмента $A_1$, также называемое головой дракона, находится в вершине $S$;

• $A_{i} = B_{i-1}$ для всех $i > 1$, то есть начало каждого следующего сегмента совпадает с концом предыдущего;

• $\left|\measuredangle \left(\overrightarrow{A_{i-1} B_{i-1}}, \overrightarrow{A_i B_i}\right)\right| < 45^\circ$, то есть угол между векторами оснований соседних сегментов строго меньше $45^\circ$;

• $\left|\measuredangle \left(\overrightarrow{A_1 A_i}, \overrightarrow{A_i B_i}\right)\right| < 45^\circ$, то есть угол между вектором от головы дракона $A_1$ до начала сегмента и основанием сегмента строго меньше $45^\circ$.

Обратите внимание, что здесь углы взяты по модулю, то есть каждый следующий сегмент может быть повернут относительно предыдущего на менее чем $45^\circ$ как по, так и против часовой стрелки.

Мощностью дракона будем считать сумму квадратов длин оснований его сегментов, то есть $\sum |A_i B_i|^2$. В заданном графе помогите Канеки найти дракона максимальной мощности с головой в вершине $S$.

Формат входных данных
В первой строке входных данных даны три числа $n, m, S$ ($2 \leqslant n \leqslant 2\cdot 10^5$; $1 \leqslant m \leqslant 4\cdot 10^5$; $1 \leqslant S \leqslant n$) — количество вершин и ребер в заданном графе и номер вершины, являющейся головой дракона.

В следующих $n$ строках дано описание вершин графа. Каждая строка содержит два целых числа $x_i$ и $y_i$ — координаты $i$-й вершины ($0 \leqslant x_i, y_i \leqslant 10^9$). Гарантируется, что все вершины графа различны, то есть не существует двух вершин, обе координаты которых совпадают.

Далее следует пустая строка.

В следующих $m$ строках дано описание ребер графа. Каждая строка содержит два целых числа $u_i$ и $v_i$ — номера вершин, соединенных $i$-м ребром ($1 \leqslant u_i, v_i \leqslant n$; $u_i \neq v_i$). Гарантируется, что граф не содержит кратных ребер.

Формат выходных данных
В первой строке выходных данных выведите два числа $k$ и $ans$ — количество сегментов в драконе, имеющем максимальную мощность, и само значение его мощности.

В следующих $k$ строках выведите описание сегментов в том порядке, в котором они образуют дракона. В качестве описания сегмента $i$ выведите номера вершин $L_i$, $B_i$ и $R_i$.

Будем считать, что дракон может состоять только из вершины $S$. В таком случае количество сегментов и его мощность следует считать нулями.

Замечание
Графы, данные в первом, втором и третьем тесте условий, выглядят следующим образом.

• В первом тесте в качестве максимального дракона можно взять весь граф целиком;

• Во втором тесте ни одна тройка ребер не может быть взята в сегмент, так как не выполняется одно из обязательных условий;

• В третьем тесте максимальный дракон состоит из двух сегментов с основаниями $9 \to 5$ и $5 \to 1$ с лапами $(9 \to 8, 9 \to 7)$ и $(5 \to 3, 5 \to 2$).

2 19
2 3 4
5 6 7

0 0

2 14
8 5 7
3 1 2