CF843D Dynamic Shortest Path
Description
You are given a weighted directed graph, consisting of $ n $ vertices and $ m $ edges. You should answer $ q $ queries of two types:
- 1 v — find the length of shortest path from vertex $ 1 $ to vertex $ v $ .
- 2 c $ l_{1}\ l_{2}\ ...\ l_{c} $ — add $ 1 $ to weights of edges with indices $ l_{1},l_{2},...,l_{c} $ .
Input Format
The first line of input data contains integers $ n $ , $ m $ , $ q $ ( $ 1
Output Format
For each query of first type print the length of the shortest path from $ 1 $ to $ v $ in a separate line. Print -1, if such path does not exists.
Explanation/Hint
The description of changes of the graph in the first sample case:
The description of changes of the graph in the second sample case:
