Задача №115296. Перерисованный граф
На одном очень скучном уроке по математике Маша нарисовала у себя в тетради неориентированный граф с \(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