Послідовність триангуляції#6393
Тріангуляція багатокутника — це процес проведення відрізків між його вершинами, щоб розділити багатокутник на трикутники. Ці відрізки мають знаходитись всередині багатокутника, не перетинаючись між собою, і торкатися сторін багатокутника лише у вершинах. Наприклад:
На прикладі жирною лінією показані межі багатокутника, а тонкими — тріангуляції. При тріангуляції багатокутника з вершинами утворюється (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
Напишіть програму, яка за послідовністю з натуральних чисел визначить, чи є вона трикутною послідовністю тріангуляції багатокутника з вершинами. Якщо відповідь позитивна, виведіть список трикутників у тріангуляції в лексикографічному порядку.
Перший рядок містить кількість тестів (1 \leq p \leq 1000).
Кожен тест складається з одного рядка, що містить номер тесту , кількість чисел у послідовності (4 \leq n \leq 20), а також самі цілих чисел послідовності у відповідному порядку, розділені пробілом.
Для кожного тесту виведіть кілька рядків. Якщо вхідна послідовність НЕ є трикутною для -кутника, виведіть номер тесту , пробіл і велику літеру N. Інакше в першому рядку виведіть номер тесту , пробіл і велику літеру 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)
Приклад 1