Loading [MathJax]/jax/output/CommonHTML/jax.js

Задача E. T-пути

Автор:Жюри летних сборов 2009   Ограничение времени:2 сек
Входной файл:tpath.in   Ограничение памяти:256 Мб
Выходной файл:tpath.out  
Максимальный балл:100  

Условие

Задан неориентированный невзвешенный связный граф G=(V,E) с выделенным множеством вершин TV. T-путь — простой путь, начинающийся и заканчивающийся в различных вершинах множества T. Найдите длину кратчайшего T-пути в графе, а также остаток количества различных кратчайших T-путей по модулю 1000000007.

Формат входного файла

В первой строке записаны числа n, m, t — количество вершин, рёбер графа и размер множества T соответственно. На второй строке записаны t различных чисел — элементы множества T. На следующих m строках записаны пары чисел x, y — номера вершин, соединённых ребром (xy, 1x,yn). В графе нет петель и кратных ребер.

Формат выходного файла

Выведите два числа — длину кратчайшего T-пути и количество различных кратчайших T-путей по модулю 1000000007.

Ограничения

2n105;

1m5105;

2tn;

Примеры тестов

Входной файл (tpath.in) Выходной файл (tpath.out)
1
4 4 2
1 3
1 2
2 3
3 4
4 1
2 2
2
5 5 3
5 1 3
1 2
2 3
5 2
3 4
4 1
2 4

0.060s 0.009s 13