Дороги з одностороннім рухом
Судиславль страждає від жахливих пробок. Рік за роком ситуація погіршується, і міська влада вирішила прийняти міри. Було вирішено зробити рух на усіх вулицях одностороннім, щоб впоратись з проблемою. На жаль, вони не спланували це належним чином і ризикують залишити деякі частини міста недоступними з інших. У зв'язку з цим міністерство транспорту підготувало список пар перехресть міста, які повинні бути зв'язними після операції.
Напишіть програму, яка орієнтує усі вулиці міста так, що усі вимаги залишаються задоволеними.
Вхідні дані
Перший рядок вводу містить три цілих числа 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. Зверніть увагу, що порядок вулиць повинен бути таким же, як і у вхідних даних. Якщо існує декілька варіантів розв'язку, виведвть довільний з них.