305086: CF962F. Simple Cycles Edges

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Simple Cycles Edges

题意翻译

定义无向图中简单环为每个顶点只包含了一次的环(即除起点和终点外每个点只经过一次的回路)。 现给出一张 $n$ 个点 $m$ 条边的图($n,m\leqslant100000$),求恰好被包含在一个(多了少了都不行)简单环中的边,第一行输出这些边个数,第二行根据输入顺序输出这些边编号。 数据保证无重边自环,但不一定保证连通。 感谢 @cy1366371760 提供的翻译。

题目描述

You are given an undirected graph, consisting of $ n $ vertices and $ m $ edges. The graph does not necessarily connected. Guaranteed, that the graph does not contain multiple edges (more than one edges between a pair of vertices) or loops (edges from a vertex to itself). A cycle in a graph is called a simple, if it contains each own vertex exactly once. So simple cycle doesn't allow to visit a vertex more than once in a cycle. Determine the edges, which belong to exactly on one simple cycle.

输入输出格式

输入格式


The first line contain two integers $ n $ and $ m $ $ (1 \le n \le 100\,000 $ , $ 0 \le m \le \min(n \cdot (n - 1) / 2, 100\,000)) $ — the number of vertices and the number of edges. Each of the following $ m $ lines contain two integers $ u $ and $ v $ ( $ 1 \le u, v \le n $ , $ u \neq v $ ) — the description of the edges.

输出格式


In the first line print the number of edges, which belong to exactly one simple cycle. In the second line print the indices of edges, which belong to exactly one simple cycle, in increasing order. The edges are numbered from one in the same order as they are given in the input.

输入输出样例

输入样例 #1

3 3
1 2
2 3
3 1

输出样例 #1

3
1 2 3 

输入样例 #2

6 7
2 3
3 4
4 2
1 2
1 5
5 6
6 1

输出样例 #2

6
1 2 3 5 6 7 

输入样例 #3

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

输出样例 #3

0

Input

题意翻译

定义无向图中简单环为每个顶点只包含了一次的环(即除起点和终点外每个点只经过一次的回路)。 现给出一张 $n$ 个点 $m$ 条边的图($n,m\leqslant100000$),求恰好被包含在一个(多了少了都不行)简单环中的边,第一行输出这些边个数,第二行根据输入顺序输出这些边编号。 数据保证无重边自环,但不一定保证连通。 感谢 @cy1366371760 提供的翻译。

加入题单

上一题 下一题 算法标签: