Некоторое время назад Гомер жил в красивом городе. В нем есть \(n\) домов, пронумерованных от \(1\) до \(n\), а также \(m\) ориентированных дорог. Каждая дорога имеет положительную длину и всегда направлена от дома с меньшим индексом к дому с большим. Для каждых двух (разных) домов между ними есть максимум одна дорога.
Гомер обнаружил, что для некоторых двух чисел \(L\) и \(R\) такой город может быть \((L, R)\)-непрерывным.
Город называется \((L, R)\)-непрерывным, если выполняются два условия:
- все пути от дома \(1\) до дома \(n\) имеют длину от \(L\) до \(R\) (включительно);
- для каждого целого \(L \leq d \leq R\) есть ровно один путь от дома \(1\) до дома \(n\) с длиной равной \(d\).
Путь от дома \(u\) к дому \(v\) — это последовательность \(u = x_0 \to x_1 \to x_2 \to \dots \to x_k = v\), где для каждого \(1 \leq i \leq k\) есть дорога от дома \(x_{i-1}\) к дому \(x_{i}\). Длина пути — это сумма длин всех дорог в пути. Два пути \(x_0 \to x_1 \to \dots \to x_k\) и \(y_0 \to y_1 \to \dots \to y_l\) считаются различными, если \(k \neq l\), или \(x_i \neq y_i\) для какого-то \(0 \leq i \leq \min\{k, l\}\).
Переехав в другой город, Гомер запомнил только числа \(L\) и \(R\), но забыл число домов \(n\), число дорог \(m\), а также то, как дома соединены дорогами. Однако он считает, что количество домов должно быть не больше \(32\) (потому что город маленький).
Как лучший друг Гомера, пожалуйста, скажите ему, может ли существовать \((L, R)\)-непрерывный город, или нет.
Выходные данные
Если невозможно найти \((L, R)\)-непрерывный город c не более \(32\) домами, выведите «NO».
В противном случае в первой строке выведите «YES», а затем описание \((L, R)\)-непрерывного города.
Вторая строка должна содержать два целых числа \(n\) (\(2 \leq n \leq 32\)) и \(m\) (\(1 \leq m \leq \frac {n(n-1)} 2\)), где \(n\) обозначает количество домов, а \(m\) — количество дорог.
Затем должно следовать \(m\) строк. \(i\)-я из \(m\) строк должна содержать три целых числа \(a_i\), \(b_i\) (\(1 \leq a_i < b_i \leq n\)) и \(c_i\) (\(1 \leq c_i \leq 10^6\)), обозначающие направленную дорогу от дома \(a_i\) к дому \(b_i\) длиной \(c_i\).
Требуется, чтобы для каждых двух домов было не более одной дороги, соединяющей их. Иначе говоря, для каждых \(1 \leq i < j \leq m\), либо \(a_i \neq a_j\), либо \(b_i \neq b_j\).
Примечание
В первом примере существует только один путь от дома \(1\) до дома \(n = 2\), а его длина составляет \(1\).
Во втором примере есть три пути от дома \(1\) до дома \(n = 5\), а именно \(1 \to 2 \to 5\) длиной \(4\), \(1 \to 3 \to 5\) длиной \(5\), и \(1 \to 4 \to 5\) длиной \(6\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 1
|
YES
2 1
1 2 1
|
|
2
|
4 6
|
YES
5 6
1 2 3
1 3 4
1 4 5
2 5 1
3 5 1
4 5 1
|