Судиславль страдает от ужасных пробок. Год за годом ситуация ухудшается, и городские власти решили принять меры. Они решили сделать движение на всех улицах односторонним, чтобы справиться с проблемой. К сожалению, они не спланировали это должным образом и рискуют оставить некоторые части города недоступными из других. В связи с этим министерство транспорта подготовило список пар перекрёстков города, которые должны быть связными после операции.
Напишите программу, которая ориентирует все улицы города так, что все требования остаются удовлетворены.
Первая строка ввода содержит три целых числа n, m и k (1 ≤ n ≤ 50000, 0 ≤ m, k ≤ 200000), задающих число перекрёстков города, улиц и требований соответственно. Перекрёстки пронумерованы от 1 до n. Следующие mстрок содержат пары чисел a_i, b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i), описывающих одну улицу. Изначально все улицы двунаправленные. Существует не более одной дороги между каждой парой перекрёстков. Следующие k строк описывают требования. Каждая из них содержит пару целых чисел p_i, q_i (1 ≤ p_i, q_i ≤ n, p_i ≠ q_i), означающих, что после того, как улицы станут однонаправленными должен существовать путь из p_i в q_i.
Выведите в первой строке YES либо NO, в зависимости от того, можно ли так определить одностороннее движение на всех улицах, чтобы удовлетворить все требования. Если это возможно, выведите ещё m строк, содержащих парыc_i, d_i - описание, как направить движение на i-й улице из ввода. Это значит, что движение по улице должно быть возможно от перекрёстка c_i к перекрёстку d_i. Обратите внимание, что порядок улиц должен быть таким же, как и на входе. Если существует несколько вариантов решения, выведите любой из них.