問題一覧 > 通常問題

No.2290 UnUnion Find

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 140
作問者 : t98slidert98slider / テスター : 👑 箱
12 ProblemId : 9133 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-05-12 01:57:05

問題文

$N$ 頂点 $0$ 辺のグラフ $G$ が与えられます。頂点には $1$ から $N$ までの番号が付いています。
以下の形式のクエリが $Q$ 個与えられるので、グラフ $G$ に対して順に処理してください。

  • 1 u v : 頂点 $u$ と頂点 $v$ を辺で結ぶ。
  • 2 v : 頂点 $v$ と連結ではない頂点をひとつ出力してください。存在しない場合は-1を出力してください。

入力

$N\ \ Q$
${\rm Query}_{1}$
${\rm Query}_{2}$
${\rm Query}_{3}$
$\ \ \ \ \vdots$
${\rm Query}_{i}$
$\ \ \ \ \vdots$
${\rm Query}_{Q}$

  • $1\leq N \leq 2\times 10^{5}$
  • $1\leq Q \leq 2\times 10^{5}$
  • ${\rm Query}_{i}$について

    タイプ1のクエリのとき
    $1\ u_{i}\ v_{i}$
    タイプ2のクエリのとき
    $2\ \ v_{i}$
    ・$1 \leq u_{i}, v_{i} \leq N$

  • 入力はすべて整数

出力

タイプ2のクエリが $K$ 個与えられた場合、$i\ (1 \leq i \leq K) $ 行目に $i$ 個目のタイプ2のクエリの回答を出力してください。解が複数存在する場合、どれを出力しても正答とみなされます。最後に改行してください。

サンプル

サンプル1
入力
4 7
2 1
1 1 2
2 1
1 3 4
2 4
1 1 3
2 1
出力
2
3
1
-1

  • 1つ目のクエリでは、頂点 $1$ と連結でない頂点の出力が求められます。頂点 $1$ と連結でない頂点である $2$ , $3$ , $4$ のいずれかを出力します。
  • 2つ目のクエリでは、頂点 $1$ と頂点 $2$ が辺で結ばれます。
  • 3つ目のクエリでは、頂点 $1$ と連結でない頂点の出力が求められます。頂点 $1$ と連結でない頂点である $3$ , $4$ のいずれかを出力します。
  • 4つ目のクエリでは、頂点 $3$ と頂点 $4$ が辺で結ばれます。
  • 5つ目のクエリでは、頂点 $4$ と連結でない頂点の出力が求められます。頂点 $4$ と連結でない頂点である $1$ , $2$ のいずれかを出力します。
  • 6つ目のクエリでは、頂点 $1$ と頂点 $3$ が辺で結ばれます。
  • 7つ目のクエリでは、頂点 $1$ と連結でない頂点の出力が求められます。頂点 $1$ と連結でない頂点は存在しないため $-1$ を出力します。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。