問題一覧 > 通常問題

No.1254 A Bridge to Reinforcement

レベル : / AI推定難易度 : 1100 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 146
作問者 : 👑 Kazun / テスター : QCFium
お気に入りにしたユーザー ProblemId : 4690 / 自分の提出
問題文最終更新日: 2020-11-07 01:05:02
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 269 (MATHEMATICS 1) (順位表) の他の問題:

Problem Statement

Yuki Country is an island nation consisting of $N$ islands, and the $N$ islands are named Island 1, $\dots$ , Island $N$. Yuki Country also has $N$ wooden bridges connecting islands, named Bridge 1, $\dots$ , Bridge $N$, and Bridge $i$ connects Island $a_i$ and Island $b_i$, making travel between these 2 islands possible. Currently, thanks to the $N$ bridges, any 2 islands can be reached from each other by using some number of bridges.

Since the seas of Yuki Country are rough and bridges are easily destroyed, it has been decided to reinforce the wooden bridges into iron bridges. As one criterion for deciding which bridges to prioritize for reinforcement, it was judged that the reinforcement of bridges satisfying the following condition should be prioritized.
$\quad$[Condition] If only Bridge $i$ breaks and travel using Bridge $i$ becomes impossible, then moving from some Island $p$ to some Island $q$ becomes impossible no matter how many bridges are used.
In this case, how many bridges should not be prioritized for reinforcement, and which bridges are they?

Constraints

  • $3 \leq N \leq 10^5$
  • $1 \leq a_i,b_i \leq N,~a_i \neq b_i$
  • Bridge $i$ connects Island $a_i$ and Island $b_i$.
  • For any $1 \leq p,q \leq N,p \neq q$, there is at most 1 bridge directly connecting the 2 islands, Island $p$ and Island $q$.
  • The given information satisfies the conditions described in the problem statement. (Changed at 21:39: "above" → "described in the problem statement")
  • All inputs are integers.

Input

The input is given from standard input in the following format.
$N$
$a_1~b_1$
$\vdots$
$a_N~b_N$

Output

If there are $K$ bridges that should not be prioritized and they are Bridge $p_1$,$\dots$,Bridge $p_K$, output them as follows.

$K$
$p_1~\dots~p_K$
The $K$ bridge numbers may be output in any order, but the same number must not be output 2 or more times. Also, output a newline after $p_K $ as well.
* Note that you must output the bridges that should not be prioritized.

Sample

Sample 1
Input
4
1 2
1 3
1 4
2 3
Output
3
1 2 4

If Bridge 3 breaks, it becomes impossible to go from Island 1 to Island 4.

Sample 2
Input
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 1
Output
8
1 2 3 4 5 6 7 8

No matter which bridge breaks, it is possible to go from any island to any other island.

Sample 3
Input
6
1 6
2 6
3 6
4 6
5 6
1 2
Output
3
1 2 6

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