Hamako Online Judge

TLE
0.5sec

MLE
64MB

得点
1825

Aphorismus

条約が有効なのは私にとって有益な間だけだ。

── アドルフ・ヒトラー

問題

ここはGroßdeutsches Reichです。
偉大なる総統 Adolf Hitler が統治しています。

国内には $N$ 個の都市があり、$M$ 本の一方通行の道が都市を結んでいます。
道が一方通行なのは大変不便です。
総統は相当慈悲深く、民族のために総力を挙げて双方向に通行可能な道を開発しました。
これを Autobahn と呼びます。

政府はいくつかの Autobahn を建設することにしましたが、やはり民族の生活をゆたかで便利なものにするために開発したので、便利さを評価したいです。
そこで「都市 $s$ と都市 $t$ が便利である」ことを以下のように定義することにしました。

都市 $s$ を出発して都市 $t$ に行き、再び都市 $s$ に戻ってくることができる。

総統は以下2つの総統命令のうちどちらかを、$Q$ 回行います。

総統命令1 : 都市 $a,\ b$ 間に Autobahn を建設せよ。
総統命令2 : 都市 $s$ と都市 $t$ が便利かどうか報告せよ。

ところで総統は非アーリア的なものが嫌いです。
非アーリア的な道を排除する総統命令を出すことにしました。
都市 $v$ から都市 $u$ へと向かう道が非アーリア的かどうかを以下のように定義することにします。

都市 $v$ と都市 $u$ が便利でない。

この総統命令は Nero 指令と呼ぶことにします。
名誉アーリア人であるあなたは、恐れ多くも、これらの Projekte の責任者に任命されました。
総統の期待に応えるべく、ミスなく順番に仕事をこなしましょう。

順番は

Nero 指令を実行する。
総統命令1と総統命令2を与えられた順に実行する。

です。
ミスをするのは非アーリア的な行動なので気を付けましょう。

入力

入力は以下の形式で標準入力から与えられる。

$N\ M$
$v_1\ u_1$
$v_2\ u_2$
......
$v_M\ u_M$
$Q$
$f_1$
$f_2$
......
$f_Q$

$1$ 行目に都市の数 $N$ と一方通行の道の数　$M$ が与えられます。
続く $M$ 行には道の情報 $v,\ u$ が与えられます。
これは $v_i$ から $u_i$ に一方通行の道がつながっていることを示します。
その後総統命令の数 $Q$ が与えられます。
続く $Q$ 行には総統命令の情報 $f$ が以下の形式で与えられます。

総統命令1

1 $a_i\ b_i$

これは都市 $a_i,\ b_i$ 間に Autobahn を建設することを示します。

総統命令2

2 $s_i\ t_i$

これは都市 $s_i$ と都市 $t_i$ が便利かどうかを報告することを示します。

出力

総統命令2が与えられるたびに、$2$都市が便利なら $1$を、便利でないなら $0$ を一行に出力してください。
改行を忘れずに。

制約

全ての入出力ケースについて以下を満たす。

$2 \leq N \leq 10^5$
$0 \leq M \leq 10^5$
$1 \leq Q \leq 2 \times 10^5$
$1 \leq v_i,\ u_i \leq N ( 1 \leq i \leq M )$
$1 \leq a_i,\ b_i,\ s_i,\ t_i \leq N ( 1 \leq i \leq Q )$
$v_i \neq u_i$
$a_i \neq b_i$
$s_i \neq t_i$
少なくとも1回総統命令2が与えられる

入出力例

入力例1

出力例1

1
0
1

はじめは
　1 ←→ 2　　　3
のようになっています。
ですので都市 $1,\ 2$ は便利で、都市 $1,\ 3$ は便利ではありません。
次に都市$2,\ 3$間にAutobahnを建設するので
　1 ←→ 2 ←→ 3
のようになります。
したがってこのとき都市 $1,\ 3$ は便利です。

入力例2

出力例2

1
0
1

同じ都市間に道がある場合もあります。
すでに道がある都市間に autobahn が建設される場合もあります。

1404 - 国家社会主義