Неизбежные печати
Дан неориентированный граф из N залов и M двусторонних коридоров. У каждого коридора есть положительный вес.
Для запроса s, t коридор считается неизбежным, если он встречается в любом маршруте из s в t. Маршрут может повторно посещать вершины и рёбра. При s=t разрешён пустой маршрут.
Для каждого запроса найдите количество неизбежных коридоров и сумму их весов.
Входные данные
В первой строке N, M, Q (1 <= N,Q <= 100000, 0 <= M <= 200000). Далее M строк: u v w — концы коридора и его вес (1 <= w <= 10^9). Между двумя залами не более одного коридора. Затем Q строк с парами s t.
Выходные данные
Для каждого запроса выведите количество неизбежных коридоров и сумму их весов. Если пути нет, выведите -1 -1. Если путь есть, но неизбежных коридоров нет, выведите 0 0.
| № | Входные данные | Выходные данные |
|
1
|
8 9 4
1 2 4
2 3 6
3 1 9
3 4 7
4 5 2
5 6 5
6 4 8
6 7 11
5 8 13
1 7
4 6
8 7
5 5
|
2 18
0 0
2 24
0 0
|
|
2
|
4 1 3
1 2 10
1 3
1 2
3 3
|
-1 -1
1 10
0 0
|