408761: GYM103295 I Sling Ring

Stephen finds a slightly defective sling ring while training at Kamar-Taj that will open portals, but going through each portal takes time rather than being instant. Portals are bidirectional so that someone on either side can get through to the other side. To practice, he opens a bunch of portals between various locations of interest. However, he isn't well trained enough yet to maintain all of the portals, so the portals begin to collapse over time.

Stephen wonders how quickly he can get between any two arbitrary locations as the portals are collapsing. Can you help him?

First line contains $$$N, M, Q$$$, the number of locations, portals, and queries. $$$ 2 \leq N \leq 300, 1 \leq M \leq Q \leq 10000$$$

The next $$$M$$$ lines are in the form $$$u_i$$$ $$$v_i$$$ $$$w_i$$$, indicating a portal from location $$$u_i$$$ to $$$v_i$$$ (0 indexed) that takes $$$w_i$$$, $$$0 \leq u_i, v_i < N$$$ and $$$0 \leq w_i \leq 10000$$$.

Then the next $$$Q$$$ lines are in the form $$$q$$$ $$$u_i$$$ $$$v_i$$$, where $$$q$$$ being 0 indicates a portal collapse between $$$u_i$$$ and $$$v_i$$$ and 1 for a query for fastest to get from $$$u_i$$$ to $$$v_i$$$. It is guaranteed that there will be $$$M$$$ lines where $$$q$$$ is 0, i.e. all portals will collapse.

For each query where $$$q$$$ is 1, print the quickest you can get from location $$$u_i$$$ to $$$v_i$$$. If you cannot get from $$$u_i$$$ to $$$v_i$$$, print IMPOSSIBLE.

3 3 6
0 1 1
0 2 3
1 2 1
1 0 2
0 1 2
1 0 2
0 0 1
0 0 2
1 0 2

2
3
IMPOSSIBLE