Организация перевозок
Организация перевозок
В некоторой стране планирует начать работу новое торгово-промышленное предприятие: в N городах, в которых хорошо развита промышленность, открываются заводы, а в других N городах, благоприятных для торговли, открывается N торговых центров. Согласно плану, один завод будет обслуживать ровно один торговый центр.
Необходимо разбить заводы и торговые центры на пары и проложить маршруты для грузового транспорта.
Задача осложняется тем, что система дорог в стране крайне не развита – в стране M городов и всего M–1 междугородняя трасса, каждая из которых соединяет два города. Хорошо то, что любые два города при этом достижимы друг из друга. Но и это еще не все. Учитывая сложную ситуацию с дорогами, власти страны активно борются с пробками, потому через один город предприятию не разрешается прокладывать более одного маршрута.
Определите, возможно ли разработать систему маршрутов, удовлетворяющую вышеуказанным условиям.
Входные данные
В первой строке два целых числа M (2 ≤ M ≤ 10^5) и N (1 ≤ N ≤ M/2) – количество городов и количество заводов. Далее M–1 строка по два целых числа от 1 до M через пробел – пары городов, соединенных трассами. Далее две строки по N чисел через пробел – номера городов, в которых будут расположены заводы, и номера городов, в которых будут расположены торговые центры.
Выходные данные
В первой и единственной строке YES, если можно построить систему непересекающихся маршрутов, соединяющих попарно заводы и торговые центры, и NO в противном случае.
Пример
3 1 1 2 1 3 2 3
YES