Дан взвешенный ориентированный граф, состоящий из n вершин и m ребер. Требуется ответить на q запросов двух типов:
- 1 v — найти длину кратчайшего пути из вершины 1 в вершину v.
- 2 c l1 l2 ... lc — прибавить 1 к весам ребер с номерами l1, l2, ..., lc.
Выходные данные
Для каждого запроса первого типа выведите строку с одним числом — длиной кратчайшего пути от 1 до v, либо -1, если такого путь не существует.
Примечание
Иллюстрация изменений графа в первом примере из условия:
Иллюстрация изменений графа во втором примере из условия:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2 9
1 2 0
2 3 0
2 1 2
1 3
1 2
2 1 1
1 3
1 2
2 2 1 2
1 3
1 2
|
1
0
2
1
4
2
|
|
2
|
5 4 9
2 3 1
2 4 1
3 4 1
1 2 0
1 5
1 4
2 1 2
2 1 2
1 4
2 2 1 3
1 4
2 1 4
1 4
|
-1
1
2
3
4
|