Задача D. К-сеть
Задачу добавил: alef
Успешно сдано решений: 0
В НИИ большое экспериментальное производство. И для того, чтобы доставлять образцы, реактивы, небольшие инструменты и прочие нужные мелочи, существуют небольшие самоходные тележки. Тележку можно запрограммировать на движение по определенному маршруту.
Статистические исследования показали, что наиболее эффективными являются маршруты, состоящие из K "пробегов" между остановочными пунктами. Кроме того, выяснилось, что среди таких маршрутов наиболее эффективными являются маршруты, которые проходят ровно через один остановочный пункт из некоторого набора (остановочных пунктов).
Конечно, руководство НИИ хочет, чтобы количество маршрутов (а значит, задействованных тележек) было бы как можно меньше.
Ваша задача — по заданной сети маршрутов определить минимально возможное количество маршрутов, проходящих ровно через один остановочный пункт из заданного набора, которые позволяют добраться из любого остановочного пункта в любой другой остановочный пункт ровно за K пробегов.
В разных маршрутах могут присутствовать одни и те же остановки, но в одном маршруте каждая остановка может присутствовать не более одного раза.
Формат входного файла input.txt
Первая строка — целые числа N и K — количество остановочных пунктов и количество остановок в маршруте (1 <= N <= 100, 1 <= K <= 10)
Вторая строка — целое число M (1 <= M <= 20) - количество остановочных пунктов, через один из которых обязательно должен пройти маршрут, далее через пробел M целых чисел — номера этих остановочных пунктов.
Следующие N строк задают существующие между остановочными пунктами связи:
в строке #j (j = 3, 4, ..., N+2) указаны остановочные пункты, которые соединены
с пунктом #(j-2) путем для самоходной тележки. Каждая из этих N строк заканчивается нулем.
Если остановочный пункт #p присутствует в списке для пункта #q, то это означает, что самоходная тележка может проехать как из пункта #p в пункт #q, так и из пункта #q в пункт #p (даже если пункт #q отсутствует в списке для пункта #p)
Формат выходного файла output.txt
Первая строка — целое число — минимально возможное количество описанных маршрутов или слово NO, если построить набор маршрутов, удовлетворяющий условию задачи, невозможно.
Пример входного файла
11 4
3
5 3 7
2 5 3 0
1 3 4 0
7 5 6 2 4 0
0
11 1 10 0
8 3 11 0
8 0
9 6 7 0
8 10 0
9 5 0
5 6 0
Пример выходного файла
NO