No.1254 A Bridge to Reinforcement
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
Kazun
QCFium