Задача C. Вход и выход
Задачу добавил: alef
Успешно сдано решений: 0
— Значит, экскурсия может и не состояться? – спросил Кеша.
— Это почему же? – блондин рассмеялся. – Пройдем! Видеокамеры – это не главное, их днем и не включают. Ну, подойдешь ты к закрытой двери – и что? Войти надо, да и внутри не особенно погуляешь. Вот мы с Виктором, можно сказать, нашли друг друга. Даже погулять вместе можем.
— А что, можно только вдвоем выходить?
— Можно и по одному, но тогда придется объяснять, зачем, записку служебную писать. А так – наши два ключа позволяют построить несколько хороших маршрутов, – Кеша и его новые знакомые уже подошли к двери. Блондин и высокий вытащили из карманов ключи, очень похожие на ключи от домофона, только крупнее раза в четыре, и синхронно приложили их к двери. Она почти бесшумно открылась, и Кеша увидел хорошо освещенный длинный коридор.
— Видишь, все двери с такими замками, – продолжал блондин. – Говорят, что в каждой лаборатории замок должен был быть уникальным. А в дверях, которые переходы закрывают, – такие замки, чтобы их можно было только вдвоем открыть. Причем один ключ должен быть от лаборатории с одной стороны от перехода, а другой – от лаборатории с другой стороны. Секретность, в общем. Ну, на деле, конечно, все не так вышло. Взяли несколько типов замков, да и расставили их вполне случайным образом. На переходы, конечно, все правильно поставили. Ко входной двери любые два ключа подходят, лишь бы они разные были. Наверное, в смету не вписались.
— Здание все-таки не для нашего института строили. Мало ли, что там было в проекте, – заметил высокий. – Другое дело, наше начальство сочло перестройку нецелесообразной.
— А начальство не догадывается, что вы себе прогулки устраиваете? – Кеша, конечно, сомневался в этом.
— Не догадывается, конечно! – блондин вновь звонко засмеялся. – Оно просто все знает. И считает, что контакты по работе весьма полезны. Проектные группы состоят из сотрудников разных лабораторий. Так что если куда-нибудь вместе идут те, кто входит в одну проектную группу, то это считается «налаживанием и укреплением горизонтальных связей». А поскольку состав проектных групп меняется, приходится каждый раз соображать, с кем эти горизонтальные связи надо налаживать и укреплять особенно. Поскольку гулять, скажем, впятером, конечно, можно, но это все-таки многовато. Вот и решаем задачки.
Известен список сотрудников, работающих над некоторым проектом. Для каждого из сотрудников известен номер лаборатории, в которой он работает. Для каждой лаборатории известен тип замка, которым она закрывается. Лаборатории могут быть соединены друг с другом переходами. Переходы открываются всегда двумя ключами; тип одного из ключей должен совпадать с типом замка лаборатории, расположенной по одну сторону от перехода, тип второго – с типом замка лаборатории, расположенной по другую сторону от перехода (эти типы могут совпадать). Нужно подсчитать для некоторого сотрудника минимальное количество коллег, вместе с которыми он сможет выйти из здания.
Формат входного файла input.txt
Первая строка – целые числа N и L (1<=N<=100, 1<=L<=100) через пробел. N – количество сотрудников, участвующих в проекте; L – количество лабораторий в институте.
Вторая строка содержит N целых чисел через пробел – номера лабораторий, в которых работают сотрудники (каждое из чисел не превосходит L)
Третья строка содержит L целых чисел через пробел – типы замков, установленных на дверях лабораторий с соответствующими номерами.
Четвертая строка содержит целые числа K (1 <= K <= N) и V (1 <= V <= L) через пробел. K – количество сотрудников, для которых необходимо решить задачу, V – номер лаборатории, которая непосредственно соединена с выходом.
Пятая строка содержит K чисел через пробел – номера сотрудников, для которых необходимо решить задачу.
Каждая из следующих L–1 строк содержит информацию о переходах между лабораториями. Так, строка № (5 + J) содержит список лабораторий, с которыми лаборатория № J соединена переходами. В списке присутствуют только лаборатории с номерами, большими J. Если между лабораториями № J и № I существует переход, то он существует в обоих направлениях.
Формат выходного файла output.txt
Первая строка – K целых чисел через пробел. Число, стоящее на месте № J, соответствует минимальному количеству сотрудников, вместе с которыми сотрудник, номер которого стоит на месте № J в пятой строке входного файла, может отправиться на прогулку.
Если этот сотрудник не сможет отправиться на прогулку, выведите для него в качестве ответа –1
Пример входного файла
5 7
2 1 3 6 3
1 3 2 1 2 2 3
3 5
3 1 5
2 6
3 7
6
5 6
6
Пример выходного файла
1 2 1