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 Q \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.

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