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