AT_abc409_f [ABC409F] Connecting Points

$ 2 $ 次元平面上に $ N $ 頂点 $ 0 $ 辺のグラフ $ G $ があります。頂点には $ 1 $ から $ N $ までの番号が付いており、頂点 $ i $ は座標 $ (x_i,y_i) $ にあります。 $ G $ の頂点 $ u,v $ に対して、 $ u,v $ の距離 $ d(u,v) $ をマンハッタン距離 $ d(u,v)=|x_u-x_v|+|y_u-y_v| $ で定義します。 また、 $ G $ の $ 2 $ つの連結成分 $ A,B $ に対して、 $ A,B $ の頂点集合をそれぞれ $ V(A),V(B) $ としたとき、 $ A,B $ の距離 $ d(A,B) $ を $ d(A,B)=\min\lbrace d(u,v)\mid u \in V(A), v\in V(B)\rbrace $ で定義します。 以下で説明されるクエリを $ Q $ 個処理してください。クエリは次の $ 3 $ 種類のいずれかです。 - `1 a b` : $ G $ の頂点数を $ n $ としたとき、頂点 $ n+1 $ の座標を $ (x_{n+1},y_{n+1})=(a,b) $ として、 $ G $ に頂点 $ n+1 $ を追加する。 - `2` : $ G $ の頂点数を $ n $ 、連結成分数を $ m $ とする。 - $ m=1 $ のとき、`-1` を出力する。 - $ m\geq 2 $ のとき、距離が最小である連結成分をすべてマージし、その最小の距離の値を出力する。厳密には、 $ G $ の連結成分を $ A_1,A_2,\ldots,A_m $ として、 $ \displaystyle k=\min_{1\leq i\lt j\leq m} d(A_i,A_j) $ とする。同じ連結成分にない頂点の組 $ (u,v)\ (1\leq u\lt v\leq n) $ であって $ d(u,v)=k $ を満たすようなものすべてについて、頂点 $ u $ と $ v $ の間に辺を張る。その後、 $ k $ を出力する。 - `3 u v` : 頂点 $ u,v $ が同じ連結成分にあるならば `Yes` を、そうでないならば `No` を出力する。

入力は以下の形式で標準入力から与えられる。 $ \mathrm{query}_i $ は $ i $ 番目に処理するクエリである。 > $ N $ $ Q $ $ x_1 $ $ y_1 $ $ x_2 $ $ y_2 $ $ \vdots $ $ x_N $ $ y_N $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ 各クエリは以下の $ 3 $ 種類のいずれかの形式で与えられる。 > $ 1 $ $ a $ $ b $ > $ 2 $ > $ 3 $ $ u $ $ v $

問題文の指示に従ってクエリへの答えを改行区切りで出力せよ。

### Sample Explanation 1 はじめ、頂点 $ 1,2,3,4 $ はそれぞれ座標 $ (3,4),(3,3),(7,3),(2,2) $ にあります。 - $ 1 $ 番目のクエリについて、頂点 $ 1 $ と $ 2 $ は連結でないため、`No` を出力します。 - $ 2 $ 番目のクエリについて、連結成分は $ 4 $ つあり、各連結成分に含まれる頂点集合は $ \lbrace 1\rbrace, \lbrace 2\rbrace, \lbrace 3\rbrace, \lbrace 4\rbrace $ です。異なる連結成分間の距離の最小値は $ 1 $ であり、頂点 $ 1 $ と $ 2 $ の間に辺が張られます。 $ 1 $ を出力します。 - $ 3 $ 番目のクエリについて、頂点 $ 1 $ と $ 2 $ は連結であるため、`Yes` を出力します。 - $ 4 $ 番目のクエリについて、座標 $ (6,4) $ に頂点 $ 5 $ を追加します。 - $ 5 $ 番目のクエリについて、連結成分は $ 4 $ つあり、各連結成分に含まれる頂点集合は $ \lbrace 1,2\rbrace,\lbrace 3\rbrace,\lbrace 4\rbrace,\lbrace 5\rbrace $ です。異なる連結成分間の距離の最小値は $ 2 $ であり、頂点 $ 2 $ と $ 4 $ の間および頂点 $ 3 $ と $ 5 $ の間に辺が張られます。 $ 2 $ を出力します。 - $ 6 $ 番目のクエリについて、頂点 $ 2 $ と $ 5 $ は連結でないため、`No` を出力します。 - $ 7 $ 番目のクエリについて、連結成分は $ 2 $ つあり、各連結成分に含まれる頂点集合は $ \lbrace 1,2,4\rbrace,\lbrace 3,5\rbrace $ です。異なる連結成分間の距離の最小値は $ 3 $ であり、頂点 $ 1 $ と $ 5 $ の間に辺が張られます。 $ 3 $ を出力します。 - $ 8 $ 番目のクエリについて、頂点 $ 2 $ と $ 5 $ は連結であるため、`Yes` を出力します。 - $ 9 $ 番目のクエリについて、連結成分は $ 1 $ つであるため $ -1 $ を出力します。 - $ 10 $ 番目のクエリについて、座標 $ (2,2) $ に頂点 $ 6 $ を追加します。 - $ 11 $ 番目のクエリについて、連結成分は $ 2 $ つあり、各連結成分に含まれる頂点集合は $ \lbrace 1,2,3,4,5\rbrace,\lbrace 6\rbrace $ です。異なる連結成分間の距離の最小値は $ 0 $ であり、頂点 $ 4 $ と $ 6 $ の間に辺が張られます。 $ 0 $ を出力します。 ### Constraints - $ 2\leq N\leq 1500 $ - $ 1\leq Q\leq 1500 $ - $ 0\leq x_i,y_i\leq 10^9 $ - $ 1 $ 種類目のクエリについて、 $ 0\leq a,b\leq 10^9 $ - $ 3 $ 種類目のクエリについて、そのクエリを処理する直前の $ G $ の頂点数を $ n $ としたとき、 $ 1\leq u\lt v\leq n $ - 入力は全て整数