Последовательность триангуляции
Триангуляцией многоугольника называется проведение набора отрезков между его вершинами таким образом, чтобы разбить многоугольник на треугольники. Отрезки должны лежать внутри многоугольника, не пересекаться между собой, и касаться сторон многоугольника только в вершинах. Например:
В примере жирной линией показаны границы многоугольника, а тонкой приведены триангуляции. При каждой триангуляции многоугольника с n вершинами получается (n-2) треугольника.
Треугольная последовательность триангуляции получается, если начав с некоторой вершины, и двигаясь вокруг многоугольника последовательно по его вершинам, записывать количество инцидентных им треугольников. Для выше приведенного примера такими последовательностями будут (начиная сверху, слева):
A: 1 3 1 3 1 3
B: 2 2 1 4 1 2
C: 1 2 3 2 1 6 1 2 3 2 1 6
Напишите программу, которая по последовательности из n натуральных чисел определит, является ли она треугольной последовательностью триангуляции многоугольника из n вершин. Если ответ положительный, то следует вывести список треугольников в триангуляции в лексикографическом порядке.
Входные данные
Первая строка содержит количество тестов p (1 ≤ p ≤ 1000).
Каждый тест состоит из одной строки, которая содержит номер теста k, количество чисел в последовательности n (4 ≤ n ≤ 20), а также сами n целых чисел последовательности в соответствующем порядке, разделенные пробелом.
Выходные данные
Для каждого теста вывести несколько строк. Если входная последовательность НЕ является треугольной для n-угольника, то вывести номер теста k, пробел и заглавную букву N. Иначе в первой строке вывести номер теста k, пробел и заглавную букву Y. Далее вывести n - 2 строки, содержащих индексы вершин треугольников в триангуляции, по одному треугольнику в строке, индексы вершин выводить в возрастающем порядке. Треугольники сначала следует отсортировать лексикографически. Если k < l < m - индексы вершин одного треугольника, а r < s < t - индексы вершин второго, то первый треугольник предшествует второму в лексикографическом порядке, если:
k < r OR (k == r AND l < s) OR (k == r AND l == s AND m < t)