Давньогрецький ізоморфізм
Добре відомо, що улюблений граф Зевса — це решітка (а саме, граф квадратної решітки) розміром n на m. Це неорієнтований граф з n * m вершинами та n * (m - 1) + (n - 1) * m ребрами, який можна уявити як решітку з n рядками і m стовпцями, де кожен вузол з'єднаний з сусідніми вершинами.
Позначимо вершину на перетині i-го рядка і j-го стовпця як (i, j). Формально, в графі є ребра між вершинами (i, j) і (i + 1, j) для всіх 1 ≤ i < n, 1 ≤ j ≤ m, а також між вершинами (i, j) і (i, j + 1) для всіх 1 ≤ i ≤ n, 1 ≤ j < m.
(На ілюстрації зображено приклад графа квадратної решітки розміром 6 на 5)
Цікаво, що улюблений граф Посейдона також є неорієнтованим, містить n * m вершин і n * (m - 1) + (n - 1) * m ребер, і не має петель чи кратних ребер. Вершини його графа пронумеровані цілими числами від 1 до n * m.
Посейдону стало цікаво, чи можуть його граф і граф Зевса бути однаковими (ізоморфними).
Формально, його цікавить, чи існує однозначна відповідність між вершинами графа Посейдона і графа Зевса (тобто, чи можна зіставити кожній вершині графа Посейдона рівно одну вершину графа Зевса так, щоб кожна вершина графа Зевса була зіставлена рівно одній вершині графа Посейдона) так, що дві вершини суміжні в одному з цих графів тоді і тільки тоді, коли суміжні відповідні їм вершини в іншому графі.
Допоможіть Посейдону з його завданням і перевірте, чи є його граф ізоморфним графу Зевса!
Вхідні дані
У першому рядку записані два цілі числа n і m (2 ≤ n, m, n * m ≤ 2 * 10^5), що визначають розмірність решітки.
У наступних n * (m - 1) + (n - 1) * m рядках наведено опис ребер графа Посейдона. У i-му рядку записані два цілі числа u[i], v[i], що позначають ребро, яке з'єднує відповідні вершини (1 ≤ u[i], v[i] ≤ n * m, u[i] ≠ v[i]).
Гарантовано, що граф Посейдона не містить кратних ребер.
Вихідні дані
Якщо графи Посейдона і Зевса ізоморфні, виведіть "Yes". Інакше виведіть "No".
Приклад
Граф з другого прикладу зображено на картинці: