Автор: | Жюри летних сборов 2009 | Ограничение времени: | 2 сек | |
Входной файл: | tpath.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | tpath.out | |||
Максимальный балл: | 100 |
Задан неориентированный невзвешенный связный граф G = (V, E) с выделенным множеством вершин T ⊂ V. T-путь — простой путь, начинающийся и заканчивающийся в различных вершинах множества T. Найдите длину кратчайшего T-пути в графе, а также остаток количества различных кратчайших T-путей по модулю 1 000 000 007.
В первой строке записаны числа n, m, t — количество вершин, рёбер графа и размер множества T соответственно. На второй строке записаны t различных чисел — элементы множества T. На следующих m строках записаны пары чисел x, y — номера вершин, соединённых ребром (x ≠ y, 1 ≤ x, y ≤ n). В графе нет петель и кратных ребер.
Выведите два числа — длину кратчайшего T-пути и количество различных кратчайших T-путей по модулю 1 000 000 007.
2 ≤ n ≤ 105;
1 ≤ m ≤ 5 ⋅ 105;
2 ≤ t ≤ n;
№ | Входной файл (tpath.in ) |
Выходной файл (tpath.out ) |
---|---|---|
1 |
|
|
2 |
|
|