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

Автор:Жюри летних сборов 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
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.064s 0.009s 13