B - Union Find
Editorial
/
Time Limit: 5 sec / Memory Limit: 256 MB
問題文
N 人の人をいくつかのグループにします。 はじめは全員別々のグループです。
以下の 2 つのクエリを処理してください。
- B_i 番目の人を含むグループと C_i 番目の人を含むグループを 1 つのグループに統合する。
- B_i 番目の人と C_i 番目の人が同じグループかを判定する。
入力
入力は以下の形式で標準入力から与えられる。
N Q A_1 B_1 C_1 A_2 B_2 C_2 : A_Q B_Q C_Q
- 1 行目には、2 つの整数 N (1 ≦ N ≦ 10^5), Q (1 ≦ Q ≦ 10^5) が空白区切りで与えられる。
- 2 行目からの Q 行では、クエリを表す 3 個の整数 A_i(A_i=0,1), B_i(1≦B_i≦N), C_i(1≦C_i≦N) が空白区切りで与えられる。A_i=0 は統合クエリを表し、B_i 番目の人を含むグループと C_i 番目の人を含むグループを 1 つのグループに統合する。A_i=1 は判定クエリを表し、B_i 番目の人と C_i 番目の人が同じグループかを判定する。
出力
A_i=1 である i について、B_i と C_i が同じグループならば YES
を、違うグループならば NO
を出力せよ。出力の末尾に改行を入れること。
入力例1
3 3 0 1 2 1 1 2 1 1 3
出力例1
YES NO
入力例2
5 8 0 1 2 1 1 5 0 2 3 1 1 5 0 3 4 1 1 5 0 4 5 1 1 5
出力例2
NO NO NO YES