eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Организация перевозок

Организация перевозок

Лимит времени 3 секунды
Лимит использования памяти 256 MiB

В некоторой стране планирует начать работу новое торгово-промышленное предприятие: в N городах, в которых хорошо развита промышленность, открываются заводы, а в других N городах, благоприятных для торговли, открывается N торговых центров. Согласно плану, один завод будет обслуживать ровно один торговый центр.

Необходимо разбить заводы и торговые центры на пары и проложить маршруты для грузового транспорта.

Задача осложняется тем, что система дорог в стране крайне не развита – в стране M городов и всего M–1 междугородняя трасса, каждая из которых соединяет два города. Хорошо то, что любые два города при этом достижимы друг из друга. Но и это еще не все. Учитывая сложную ситуацию с дорогами, власти страны активно борются с пробками, потому через один город предприятию не разрешается прокладывать более одного маршрута.

Определите, возможно ли разработать систему маршрутов, удовлетворяющую вышеуказанным условиям.

Входные данные

В первой строке два целых числа M (2M10^5) и N (1NM/2) – количество городов и количество заводов. Далее M–1 строка по два целых числа от 1 до M через пробел – пары городов, соединенных трассами. Далее две строки по N чисел через пробел – номера городов, в которых будут расположены заводы, и номера городов, в которых будут расположены торговые центры.

Выходные данные

В первой и единственной строке YES, если можно построить систему непересекающихся маршрутов, соединяющих попарно заводы и торговые центры, и NO в противном случае.

Пример

Входные данные #1
3 1
1 2
1 3
2
3
Выходные данные #1
YES
Источник ACM ICPC 2012-2013 NEERC Siberian Group