Story

📶

SNSは便利な反面、相手の状況がわからなすぎるので危険がいっぱいです。
情報を広めるのもいいですが、デマ情報もあるしなりすましもあるし...気を付けながら使いましょう！

と言っている間に、また新たなつぶやきをした人が現れたようです。
このつぶやきはデマ情報ではないと確信し、せっかくなのであなたはこのつぶやきを拡散させることにしました。

問題

この世界でのSNSでは、$N$ 人の人が利用しています。ここで人には $1,2,\dots,N$ と番号づけられており、人 $i$ と呼びます。
$N$ 人の人がそれぞれ個別のアカウントを持っており、好きなときにメッセージを投稿できます。

また人 $x$ が人 $y$ を「フォローする」と、人 $x,y$ が互いに友達になり、双方の投稿したメッセージを見ることが可能になります。
当初はまだこのSNSは生まれたてであり、どの人も一人もフォローしていません。

ある時、人 $K$ は

【まっちゃラテ氏、5 回目の単独コンテストをMojaCoder上で開催される！！】

といった情報をつぶやきました。

この情報を求めてフォローしてきた人がいるようです。この情報を聞いた人は、フォロー関係にある人全員にその情報を伝えていきます。
そして人 $K$ 以外にも、伝えられた情報を知っている人とフォロー関係にあればその人たちにも情報を伝えられてきます。

厳密には人 $p$ が情報を知っているとき、フォロー関係にある人 $f_1,f_2,\dots,f_n$ 全員に、人 $p$ が持っている情報が伝達されていきます。

ここで $Q$ 個のSNSクエリが与えられます。順に処理してください。$j\ (1\le j\le Q)$ 個目のクエリの内容は以下のようになります。

• 1 u v : 人 $u$ が人 $v$ がフォローする。すでに人 $v$ をフォローしているなら何もしない。
• 2 : 全体の $N$ 人のうち、情報を持っている人の人数を報告する

入力

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

$\mathrm{query}_j$ は次のいずれかの形式で与えられる。

制約

• $2\le N\le 10^5$
• $1\le Q\le 3\times 10^5$
• $1\le K\le N$
• 1 u v のクエリにおいて $1\le u\lt v\le N$
• 2 のクエリは少なくとも $1$ つ以上含まれる
• すべて整数

出力

2 クエリが与えられる個数 $c$ として、$c$ 行出力せよ。$k\ (1\le k\le c)$ 行目には $k$ 個目の 2 クエリに対する答えを出力せよ。

入出力例

4 5 1
1 2 3
1 1 4
2
1 3 4
2

2
4

• $1$ 個目のクエリでは、人 $2,3$ がフォロー関係となります。

• $2$ 個目のクエリでは、人 $1,4$ がフォロー関係となります。人 $1$ は情報を持っているので、人 $4$ に伝達されます。

• $3$ 個目のクエリに対して、情報を持っている人は人 $1,4$ の $2$ 人です。

• $4$ 個目のクエリでは、人 $3,4$ がフォロー関係となります。人 $4$ は情報を持っているので、人 $3$ に伝達されます。
  また人 $3$ が情報を持ったので、人 $2$ にも伝達されます。

• $5$ 個目のクエリに対して、情報を持っている人は人 $1,2,3,4$ の $4$ 人(全員)です。

6 7 1
1 2 4
1 4 6
1 5 6
1 3 5
1 2 3
1 3 4
2

1

人 $K(=1)$ 以外、情報を知っている人はいません。