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