問題一覧 > 通常問題

No.1254 補強への架け橋

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 102
作問者 : KazunKazun / テスター : QCFiumQCFium
1 ProblemId : 4690 / 出題時の順位表
問題文最終更新日: 2020-10-09 22:09:52

問題文

Yuki国は $N$ 個の島達からなる島国で, $N$ 個の島にはそれぞれ島1, $\dots$ ,島 $N$ と名付けられている. また, Yuki国には島と島とをつなぐ木で作られた橋が $N$ 個あり,それぞれ橋1, $\dots$ ,橋 $N$ と名付けられており, 橋 $i$ は島 $a_i$ と島 $b_i$ をつなぎ, この2つの島の行き来を可能にしている. 今, $N$ 個ある橋によって, どの2つの島も橋をいくつか使ってたどり着ける.

ここで, Yuki国の海は荒れやすく橋が壊されやすいという状況から, 木の橋を鉄の橋へ補強することが決定した. このとき, 補強を優先すべき橋を決定する一つの判断材料として, 以下の条件を満たす橋の補強を優先すべきだという判断がでた.
$\quad$[条件]橋 $i$ のみが壊れ,橋 $i$ を用いる行き来が不可能になったとき,ある島 $p$ からある島 $q$ への移動を何個かの橋を利用しても不可能になってしまう.
このとき, 補強を優先すべきではない橋は何本か? またどの橋か?

制約

  • $3 \leq N \leq 10^5$
  • $1 \leq a_i,b_i \leq N,~a_i \neq b_i$
  • 橋 $i$ は島 $a_i$ と島 $b_i$ をつなぐ.
  • 任意の $1 \leq p,q \leq N,p \neq q$ に対して, 2つの島 $p$ と島 $q$ を直接結ぶ橋は高々1本である.
  • 与えられる情報は問題文に書かれている条件を満たす. (21:39 変更 「上の」→「問題文に書かれている」)
  • 入力は全て整数である.

入力

入力は以下の形式で標準入力から与えられる.
$N$
$a_1~b_1$
$\vdots$
$a_N~b_N$

出力

優先すべきではない橋が$K$個でそれが橋 $p_1$,$\dots$,橋 $p_K$ であるとき, 以下のようにして出力せよ.

$K$
$p_1~\dots~p_K$
$K$ 個の橋の番号を出力する順番は順不同とするが, 同じ番号を2回以上出力してはならない. また, $p_K $の出力の後にも改行をすること.
※優先すべきではない橋を出力することに注意せよ.

サンプル

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

橋3が壊れてしまうと, 島1から島4へ行けなくなってしまう.

サンプル2
入力
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 1
出力
8
1 2 3 4 5 6 7 8

どの橋が壊れても, 任意の島から別の島へ行くことができる.

サンプル3
入力
6
1 6
2 6
3 6
4 6
5 6
1 2
出力
3
1 2 6

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