e-olymp
Змагання

2018 School second team season olympiad, Basic nomination

Древнегреческий изоморфизм

Хорошо известно, что любимый граф Зевса - это решетка (а именно, граф квадратной решетки) n * m, то есть неориентированный граф из n * m вершин и n * (m - 1) + (n - 1) * m ребер, который можно представить в виде решетки с n строками и m столбцами, что каждый узел сетки соединен с соседними вершинами.

Обозначим за (i, j) вершину на пересечении i-й строки и j-го столбца. Формально, в графе есть ребра между (i, j) и (i + 1, j) для всех 1i < n, 1jm, и ребра между (i, j) и (i, j + 1) для всех 1in, 1j < m.

prb9067.gif

(На иллюстрации изображен пример графа квадратной решетки 6 * 5)

И как бы это ни было удивительно, но оказалось, что любимый граф Посейдона тоже является неориентированным, тоже содержит n * m вершин и n * (m - 1) + (n - 1) * m ребер, а также не содержит петель и кратных ребер. Вершины его графа пронумерованы целыми числами от 1 до n * m.

Посейдону стало интересно, а может быть его с Зевсом графы и вовсе одинаковы (изоморфны)?

Формально, ему стало интересно, можно ли найти однозначное соответствие вершин графа Посейдона и вершин графа Зевса (то есть сопоставить каждой вершине графа Посейдона ровно одну вершину графа Зевса так, чтобы каждая вершина графа Зевса была сопоставлена ровно одной вершине графа Посейдона) так, что две вершины смежны в одном из этих графов тогда и только тогда, когда смежны соответствующие им вершины в другом графе.

Помогите Посейдону с его нелегкой задачей, проверьте на изоморфизм его граф и граф Зевса!

Входные данные

В первой строке записаны два целых числа n и m (2n, m, n * m2 * 105), обозначающие размерность решетки.

В следующих n * (m - 1) + (n - 1) * m записано описание ребер графа Посейдона. В i-й из них записаны два целых числа ui, vi, обозначающие ребро, соединяющее соответствующие вершины (1ui, vin * m, uivi).

Гарантируется, что граф Посейдона не содержит кратных ребер.

Выходные данные

Если графы Посейдона и Зевса изоморфны, выведите "Yes". Иначе выведите "No".

Пример

Граф из второго примера изображен на картинке: prb9067_1.gif

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
2 2
1 2
2 3
3 4
4 2
Вихідні дані #1
No
Вхідні дані #2
4 3
2 9
2 7
5 9
5 6
7 10
1 7
1 6
1 9
1 12
6 11
10 12
11 12
8 10
4 8
4 12
3 4
3 11
Вихідні дані #2
Yes
Джерело 2018 Цикл Интернет-олимпиад для школьников, вторая командная олимпиада сезона, базовая номинация, 20 октября, Задача F