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

Условие

Задан неориентированный невзвешенный связный граф 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 ≤ 10⁵;

1 ≤ m ≤ 5 ⋅ 10⁵;

2 ≤ t ≤ n;

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

4 4 2
1 3
1 2
2 3
3 4
4 1

2 2

5 5 3
5 1 3
1 2
2 3
5 2
3 4
4 1

2 4