# Problem L

Supply Routes

During a zombie apocalypse, it is important to stay connected between strongholds. Maintaining supply routes between locations is important for survival.

You are given information about a road network: its
junctions and two-way streets that directly connect junctions.
Over time, these streets will become overrun by zombies and
become impassable. At various moments in time, you wonder if it
is *safe* to travel from junction $u$ to junction $w$ for two particular junctions.

That is, is there a sequence of junctions $u = v_1, v_2, \ldots , v_ k = w$ of any length $k$ such that for each $1 \leq i < k$ we have that $v_ i$ and $v_{i+1}$ are directly connected by a street that is not overrun by zombies?

## Input

The first line of input contains three integers $N$ ($2 \leq N \leq 2 \cdot 10^5$), $M$ ($1 \leq M \leq \min \{ 5 \cdot 10^5, N*(N-1)/2\} $) and $Q$ ($1 \leq M \leq 5 \cdot 10^5$). Here, $N$ is the number of junctions (numbered $0$ through $N-1$), $M$ is the number of streets that directly connect junctions, and $Q$ is the number of queries to process. Initially, no street is overrun by zombies.

Then $M$ lines follow, each describing a street directly connecting two junctions. The $i$th such line contains two distinct integers $u_ i, v_ i$ ($0 \leq u_ i < v_ i < N$) indicating junctions $u_ i$ and $v_ i$ are directly connected by a two-way street. No pair of junctions will be directly connected by more than one street.

Finally, $Q$ lines follow describing a sequence of events. The $j$th such line contains three integers $t_ j, u_ j, v_ j$. Here $t_ j$ will be $0$ or $1$ and $u_ j, v_ j$ will be two distinct integers ($0 \leq u_ j < v_ j < N$) indicating junctions.

If $t_ j = 0$, the street connecting $u_ j$ to $v_ j$ is now overrun and can no longer be safely travelled in either direction. You are guaranteed that in such a case, $u_ j$ and $v_ j$ will be directly connected by a street given earlier in the input and no street will be overrun more than once.

If $t_ j = 1$, then you are to report if it is possible to safely travel from $u_ j$ to $v_ j$ using only streets that have not yet been overrun by zombies (i.e. there is a path from $u_ j$ to $v_ j$ using only streets that were not overrun in an earlier step $j’ < j$).

You are guaranteed that $t_ j$ will be $1$ in at least one of these final $Q$ lines.

## Output

For each of the last $Q$ lines having $t_ j = 1$, output a single line with
the message `safe` if there is a path
from $u_ j$ to
$v_ j$ using only streets
that are not overrun by zombies. Otherwise, output a single
line with the message `unsafe`.

Sample Input 1 | Sample Output 1 |
---|---|

3 2 6 0 1 1 2 0 1 2 1 0 1 1 0 2 0 0 1 1 0 1 1 0 2 |
safe unsafe unsafe unsafe |