eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Хорошо известно, что любимый граф Зевса - это решетка (а именно, граф квадратной решетки) 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 * 10^5), обозначающие размерность решетки.

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

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

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

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

Пример

prb9067_1.gif

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

Пример

Входные данные #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