|
Лимит времени 3000/5000/5000/5000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Если новость знает кто-то один, то вскоре её узнает кто-нибудь ещё! Жители села Слухово охотно делятся новостями. Когда кто-то узнаёт какую-то новость, на следующий день он обязательно рассказывает её всем своим знакомым. Если сегодня новость известна только её автору, то завтра она будет известна всем, с кем он лично знаком. А послезавтра её узнают все знакомые всех его знакомых и т.д. Пусть N – количество жителей села и они пронумерованы числами 1,2,3,…, N. Мы хотим «вычислить» номер автора новости, если мы знаем количество дней, прошедших с момента её появления, и нам известны номера всех жителей, кто эту новость уже узнал. Формат входных данных В первой строке входного файла записаны 3 натуральных числа N, K, D, где N – количество жителей села (2 ≤ N ≤ 500), K – количество жителей, которые уже знают новость (2 ≤ K ≤ N), D – количество дней, прошедших с момента появления новости (2 ≤ D ≤ K). В следующих N строках расположена симметричная матрица А размеров NxN, состоящая из 0 и 1, у которой A[i,j] = 1 только и только тогда, когда жители i и j лично знакомы. Элементы главной диагонали матрицы А равны 0. В следующей строке в записаны в возрастающем порядке K натуральных чисел – номера всех жителей, которые узнали новость в первые D дней с момента её появления. Формат выходных данных В единственной строке выходного файла требуется записать в возрастающем порядке номера всех тех жителей села, каждый из которых теоретически мог быть автором новости. Пример
Комментарий к примеру: Автором новости мог быть либо житель 2, либо житель 4. Например, если автор новости – это житель 2, то в первый день только он один знал новость. На второй день новость от него узнали жители 4 и 5. На третий день новость от жителя 5 узнал житель 1. Таким образом, в первые 3 дня с момента появления новости она стала известна жителям 1, 2, 4 и 5. А житель 3 узнает новость только на четвёртый день. Для отправки решений необходимо выполнить вход. |