Скоро Codeforces Round 1133 (Div. 1, Div. 2)! Регистрация здесь. ×

D. Перерисованный граф
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На одном очень скучном уроке по математике Маша нарисовала у себя в тетради неориентированный граф с $$$n$$$ вершинами и $$$m$$$ ребрами. Вершины графа были пронумерованы от $$$1$$$ до $$$n$$$.

После урока она ушла на перемену, а когда вернулась, то обнаружила, что граф, кажется, изменился!

Машин сосед по парте, Паша, признался, что в её отсутствие он немного поменял граф. А именно, он выполнял следующую операцию: взять три различных вершины графа, $$$a$$$, $$$b$$$ и $$$c$$$, и после этого для каждой пары вершин $$$(a, b)$$$, $$$(b, c)$$$ и $$$(a, c)$$$ изменить соответствующее ребро: если оно было в текущем графе, удалить его, а если его не было — провести.

Эту операцию он совершил не один, а несколько (возможно, ноль или один) раз, каждый раз заново выбирая $$$a$$$, $$$b$$$ и $$$c$$$.

Маша хочет проверить слова своего соседа, поэтому просит вас найти любую последовательность действий Паши, которая могла бы превратить исходный граф в тот, что сейчас у Маши в тетради.

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

В первой строке заданы три числа — $$$n$$$, $$$m$$$ и $$$k$$$ ($$$3 \le n \le 10^5$$$; $$$0 \le m, k \le 10^5$$$) — количество вершин, количество ребер в исходном графе, и количество ребер в получившемся графе, соответственно.

Каждая из следующих $$$m$$$ строк содержит два числа, $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \neq v_i$$$), обозначающие вершины, соединенные $$$i$$$-м ребром в исходном графе.

Следующие $$$k$$$ строк содержат описание получившегося графа в том же формате. Гарантируется, что оба графа не содержат петель и кратных ребер.

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

Если действиями Паши невозможно получить второй граф из первого, в единственной строке выведите «NO».

Иначе, в первой строке выведите «YES». В следующей строке выведите количество операций $$$t$$$ ($$$0 \le t \le 2\cdot 10^5$$$), которое необходимо было совершить Паше. В каждой из следующих $$$t$$$ строк выведите по три числа — $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ ($$$1 \le a_i, b_i, c_i \le n$$$, числа $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ попарно различны), обозначающих тройку вершин, которую должен был выбрать Паша на $$$i$$$-м шаге.

Обратите внимание, что вам не требуется минимизировать количество действий Паши, однако необходимо, чтобы оно не превосходило $$$2\cdot 10^5$$$. Можно показать, что если решение существует, то существует и решение, состоящее из не более чем $$$2\cdot 10^5$$$ действий.

Примеры
Входные данные
3 0 3
1 2
2 3
3 1
Выходные данные
YES
1
1 2 3
Входные данные
4 3 3
1 2
2 3
3 4
1 3
4 2
2 3
Выходные данные
YES
2
1 3 4
1 2 4
Входные данные
3 1 1
1 2
2 3
Выходные данные
NO