Канеки смотрит на неориентированный граф на плоскости из \(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\)).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 6 1
1 1
1 2
2 4
3 3
1 6
2 7
3 6
1 2
1 3
1 4
3 5
3 6
3 7
|
2 19
2 3 4
5 6 7
|
|
2
|
5 4 5
1 3
2 3
3 3
5 3
3 1
1 5
2 5
5 3
4 5
|
0 0
|
|
3
|
10 12 9
1 1
1 2
2 2
4 2
2 3
6 3
1 4
3 4
2 6
1 8
1 5
2 5
3 5
4 5
5 6
5 9
6 9
7 9
8 9
9 10
5 8
5 7
|
2 14
8 5 7
3 1 2
|