H - K-th Largest Connected Components Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 475 点

問題文

N 頂点 0 辺の無向グラフがあります。頂点には 1 から N の番号がつけられています。

Q 個のクエリが与えられるので、与えられた順に処理してください。各クエリは以下の 2 種類のいずれかです。

  • タイプ 1 : 1 u v の形式で与えられる。頂点 u と頂点 v の間に辺を追加する。
  • タイプ 2 : 2 v k の形式で与えられる。頂点 v と連結な頂点の中で、k 番目に頂点番号が大きいものを出力する。ただし、頂点 v と連結な頂点が k 個未満のときは -1 を出力する。

制約

  • 1\leq N,Q\leq 2\times 10^5
  • タイプ 1 のクエリにおいて、1\leq u\lt v\leq N
  • タイプ 2 のクエリにおいて、1\leq v\leq N, 1\leq k\leq 10
  • 入力は全て整数

入力

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

N Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

ただし、\mathrm{query}_i は i 個目のクエリであり、以下のいずれかの形式で与えられる。

1 u v

2 v k

出力

タイプ 2 のクエリの個数を q として、q 行出力せよ。i 行目には i 個目のタイプ 2 に対するクエリの答えを出力せよ。

入力例 1

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

出力例 1

2
1
-1
4
2
-1
  • 1 個目のクエリについて、頂点 1 と頂点 2 の間に辺が追加されます。
  • 2 個目のクエリについて、頂点 1 と連結な頂点は 1,2 の 2 つです。この中で 1 番目に大きい 2 を出力します。
  • 3 個目のクエリについて、頂点 1 と連結な頂点は 1,2 の 2 つです。この中で 2 番目に大きい 1 を出力します。
  • 4 個目のクエリについて、頂点 1 と連結な頂点は 1,2 の 2 つです。3 個未満なので -1 を出力します。
  • 5 個目のクエリについて、頂点 1 と頂点 3 の間に辺が追加されます。
  • 6 個目のクエリについて、頂点 2 と頂点 3 の間に辺が追加されます。
  • 7 個目のクエリについて、頂点 3 と頂点 4 の間に辺が追加されます。
  • 8 個目のクエリについて、頂点 1 と連結な頂点は 1,2,3,4 の 4 つです。この中で 1 番目に大きい 4 を出力します。
  • 9 個目のクエリについて、頂点 1 と連結な頂点は 1,2,3,4 の 4 つです。この中で 3 番目に大きい 2 を出力します。
  • 10 個目のクエリについて、頂点 1 と連結な頂点は 1,2,3,4 の 4 つです。5 個未満なので -1 を出力します。

入力例 2

6 20
1 3 4
1 3 5
2 1 1
2 3 1
1 1 5
2 6 9
2 1 3
2 6 1
1 4 6
2 2 1
2 6 2
2 4 7
1 1 4
2 6 2
2 3 4
1 2 5
2 4 1
1 1 6
2 3 3
2 1 3

出力例 2

1
5
-1
3
6
2
5
-1
5
3
6
4
4

Score : 475 points

Problem Statement

There is an undirected graph with N vertices and 0 edges. The vertices are numbered 1 to N.

You are given Q queries to process in order. Each query is of one of the following two types:

  • Type 1: Given in the format 1 u v. Add an edge between vertices u and v.
  • Type 2: Given in the format 2 v k. Print the k-th largest vertex number among the vertices connected to vertex v. If there are fewer than k vertices connected to v, print -1.

Constraints

  • 1 \leq N, Q \leq 2 \times 10^5
  • In a Type 1 query, 1 \leq u < v \leq N.
  • In a Type 2 query, 1 \leq v \leq N, 1 \leq k \leq 10.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Here, \mathrm{query}_i is the i-th query and is given in one of the following formats:

1 u v

2 v k

Output

Let q be the number of Type 2 queries. Print q lines. The i-th line should contain the answer to the i-th Type 2 query.

Sample Input 1

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

Sample Output 1

2
1
-1
4
2
-1
  • In the first query, an edge is added between vertices 1 and 2.
  • In the second query, two vertices are connected to vertex 1: 1 and 2. Among them, the 1-st largest vertex number is 2, which should be printed.
  • In the third query, two vertices are connected to vertex 1: 1 and 2. Among them, the 2-nd largest vertex number is 1, which should be printed.
  • In the fourth query, two vertices are connected to vertex 1: 1 and 2, which is fewer than 3, so print -1.
  • In the fifth query, an edge is added between vertices 1 and 3.
  • In the sixth query, an edge is added between vertices 2 and 3.
  • In the seventh query, an edge is added between vertices 3 and 4.
  • In the eighth query, four vertices are connected to vertex 1: 1,2,3,4. Among them, the 1-st largest vertex number is 4, which should be printed.
  • In the ninth query, four vertices are connected to vertex 1: 1,2,3,4. Among them, the 3-rd largest vertex number is 2, which should be printed.
  • In the tenth query, four vertices are connected to vertex 1: 1,2,3,4, which is fewer than 5, so print -1.

Sample Input 2

6 20
1 3 4
1 3 5
2 1 1
2 3 1
1 1 5
2 6 9
2 1 3
2 6 1
1 4 6
2 2 1
2 6 2
2 4 7
1 1 4
2 6 2
2 3 4
1 2 5
2 4 1
1 1 6
2 3 3
2 1 3

Sample Output 2

1
5
-1
3
6
2
5
-1
5
3
6
4
4