Теорія графів#3074

Теорія графів

1 секунда

256 мегабайтів

Дуже легка

Серж вивчає теорію графів. Нещодавно він дізнався про радіус і діаметр графа. Розглянемо неорієнтований, невагомий, зв'язний граф $G$ . Позначимо довжину найкоротшого шляху між вершинами $s$ та $t$ як $ρ (s, t)$ . Радіус $r (G)$ графа визначається як

r (G) = v \in V min u \in V max ρ (v, u)

r(G) = \min_{v \in V} \max_{u \in V} \rho(v, u)

Діаметр $d (G)$ графа визначається як

d (G) = v, u \in V max ρ (v, u)

d(G) = \max_{v, u \in V} \rho(v, u)

Інтуїтивно, діаметр графа — це найбільша відстань, яку потрібно пройти, щоб дістатися від однієї вершини до іншої, а радіус — це найбільша відстань, яку вас можуть змусити подолати, вибравши певну центральну вершину.

Під час лекції професор довів, що $\frac{d ( G )}{2} \leq r (G) \leq d (G)$ \frac{d(G)}{2} \leq r(G) \leq d(G) для будь-якого графа $G$ . Тепер Серж цікавиться, чи існують такі значення $d$ та $r$ , що $\frac{d}{2} \leq r \leq d$ \frac{d}{2} \leq r \leq d, для яких існує граф $G$ , для якого $d (G) = d$ d(G) = d та $r (G) = r$ r(G) = r. Допоможіть йому з'ясувати це.

Вхідні дані

Вхід містить два цілих числа $d$ та $r$ ( $\frac{d}{2} \leq r \leq d \leq 50$ \frac{d}{2} \leq r \leq d \leq 50, $1 \leq r$ 1 \leq r).

Вихідні дані

Якщо існує граф із заданими радіусом і діаметром, виведіть YES у першому рядку. У другому рядку виведіть два цілих числа: $n$ ( $2 \leq n \leq 400$ 2 \leq n \leq 400) і $m$ — кількість вершин і ребер. Далі у наступних $m$ рядках вкажіть по два цілих числа — вершини, які з'єднуються відповідним ребром. Граф не повинен містити петель чи кратних ребер.

Якщо такого графа не існує, виведіть у першому рядку NO.

Приклади

Приклад

4 2

Приклад

3 1

NO

Приклад 1