Дороги з одностороннім рухом#5490

Дороги з одностороннім рухом

2 секунди

64 мегабайти

Дуже складна

Судиславль потерпає від жахливих заторів, і ситуація з кожним роком погіршується. У відповідь міська влада вирішила зробити всі вулиці односторонніми, щоб вирішити проблему. Проте без належного планування існує ризик того, що деякі частини міста стануть недоступними одна для одної. Для цього Міністерство транспорту склало список пар перехресть, які мають залишатися з'єднаними після впровадження змін.

Ваше завдання — написати програму, яка призначає напрямки на всіх вулицях міста так, щоб усі вимоги щодо з'єднаності були виконані.

Вхідні дані

Перший рядок містить три цілих числа $n$ , $m$ і $k$ ( $1 \leq n \leq 50000$ 1 \le n \le 50000, $0 \leq m, k \leq 200000$ 0 \le m, k \le 200000) — кількість перехресть у місті, вулиць і вимог щодо з'єднаності відповідно. Перехрестя пронумеровані від $1$ до $n$ . Далі $m$ рядків містять по два числа $a_{i}$ a_i, $b_{i}$ b_i ( $1 \leq a_{i}, b_{i} \leq n$ 1 \le a_i, b_i \le n, $a_{i} \neq = b_{i}$ a_i \ne b_i) — опис однієї вулиці. Спочатку всі вулиці двосторонні. Між будь-якою парою перехресть може бути не більше однієї вулиці. Наступні $k$ рядків містять вимоги щодо з'єднаності: кожен рядок містить два числа $p_{i}$ p_i, $q_{i}$ q_i ( $1 \leq p_{i}, q_{i} \leq n$ 1 \le p_i, q_i \le n, $p_{i} \neq = q_{i}$ p_i \ne q_i), що означає: після змін має існувати шлях з $p_{i}$ p_i у $q_{i}$ q_i.

Вихідні дані

У першому рядку виведіть YES або NO — чи можна всі вулиці направити так, щоб виконати всі вимоги. Якщо таке можливо, виведіть ще $m$ рядків: у $i$ -му рядку два числа $c_{i}$ c_i, $d_{i}$ d_i — напрямок $i$ -ї вулиці у вхідних даних (тобто рух має здійснюватися від $c_{i}$ c_i до $d_{i}$ d_i). Порядок вулиць має співпадати з порядком у вхідних даних. Якщо існує кілька рішень, виведіть будь-яке з них.

Приклади

Приклад 1