この問題ではUnionFindを問います。

まず考えられるものとしては、DFS(深さ優先探索)を行うことです。
しかしこれをクエリ毎に計算してしまうと $O(N)$ だけかかり、全体で $O(NQ)$ となってしまいます。
今回の制約下ではこのままでは時間制限に間に合いません。

そこでまず、問題に対して考察をしていきます。
今回情報を持っている人は人 $K$ の $1$ 人だけです。なので、最初は人 $K$ とフォロー関係にならない限り他の人は情報を持ちません。
そのため、情報を持っている基準となる人は人 $K$ のみということになります。

こう考えると、人 $K$ とフォロー関係にある人だけが今回の問題の答えとなる対象となることがわかります。
この処理を高速にするためのデータ構造として、UnionFindがあげられます。

UnionFindは次のような処理を高速化することができます。

• 頂点 $x,y$ を互いに繋ぐ
• 頂点 $x$ から頂点 $y$ まで、隣接する辺のみをたどっていけるか判定する
  • 言い換えると、頂点 $x$ のグループに頂点 $y$ が属しているか判定する

この他にも、頂点 $x$ が属するグループの頂点数を高速に計算することが可能です。

これより、UnionFindを用いてこの問題を正解することができます。具体的には、各クエリに対して次のような処理を行えばよいです。

• 1 u v : UnionFind に対して頂点 $u,v$ を相互に繋ぐ※
• 2 : UnionFind に対して頂点 $K$ が属するグループの頂点数を出力する

以上より、この問題を $O(Q\alpha(N))$ ※で正解することができます。

解答例(C++):

※1 相互に繋ぐとありますが、UnionFindは通常は無向グラフに対して処理を行うので、単に $u,v$ を隣接すると読み替えても構いません。
※2 $\alpha(N)$ はアッカーマンの逆関数を表します