Codeforces Round 310 (Div. 1) |
---|
Закончено |
Андроид Андреид — известный на всю галактику детектив. Сейчас он занимается подготовкой защиты от возможной атаки хакеров на важную компьютерную сеть.
В этой сети n узлов, некоторые пары узлов связаны m двусторонними каналами связи. По этой сети планируется передать q важных сообщений, i-е из которых должно быть отправлено из узла si в узел di с помощью одного или нескольких каналов связи, возможно через некоторые промежуточные узлы.
Для защиты от нападения был разработан специальный алгоритм. К сожалению его можно применить только к сети, состоящей из односторонних каналов связи. Поэтому, так как новые каналы связи создавать нельзя, было принято решение для каждого из существующих двусторонних каналов оставить возможность передавать данные только в одном из двух существующих направлений.
Перед Вами стоит задача определить, возможно ли так задать направление для каждого канала связи, чтобы каждое из q сообщений можно было успешно передать.
В первой строке заданы три целых числа n, m и q (1 ≤ n, m, q ≤ 2·105) — количество узлов, каналов связи и важных сообщений.
В следующих m строках заданы по два целых числа vi и ui (1 ≤ vi, ui ≤ n, vi ≠ ui), означающих что между узлами vi и ui есть канал связи. Между парой узлов может существовать более одного канала связи.
В следующих q строках заданы по два целых числа si и di (1 ≤ si, di ≤ n, si ≠ di) — номера узлов источника и назначения соответствующего сообщения.
Не гарантируется, что исходно возможно передать все сообщения.
Если решение существует, выведите в единственной строке "Yes" (без кавычек). Иначе выведите "No" (без кавычек).
4 4 2
1 2
1 3
2 3
3 4
1 3
4 2
Yes
3 2 2
1 2
3 2
1 3
2 1
No
3 3 2
1 2
1 2
3 2
1 3
2 1
Yes
В первом тесте из условия каналам можно задать направление, например, следующим образом: 1 → 2, 1 → 3, 3 → 2, 4 → 3. Тогда для первого сообщения будет путь 1 → 3, а для второго — 4 → 3 → 2.
В третьем тесте из условия каналам можно задать направление, например, следующим образом: 1 → 2, 2 → 1, 2 → 3. Тогда для первого сообщения будет путь 1 → 2 → 3, а для второго — 2 → 1.
Название |
---|