#P6379. [PA2010] Planning the Roadworks【征集 spj】

[PA2010] Planning the Roadworks【征集 spj】

题目背景

本题征集 SPJ,暂时无法评测。

如果您有意提供 SPJ,请在讨论区发帖或私信管理员。

题目描述

给定一个 nn 个点,mm 条边的有向图,求一个极大的可行边集使得删去这个边集之后原图连通性不变(能达到的仍然能到达)。

请给出一种可行的方案。

输入格式

第一行两个整数 nn,mm

接下来 mm 行,每行两个数 x,yx,y,表示存在一条从 xxyy 的有向边。

输出格式

本题存在 Special Judge

请在第一行输出一个整数 kk,表示边集的大小。

接下来 kk 行,每行输出一个整数 eie_i,表示删掉输入的第 eie_i 条边。

输入的边的编号从 11 开始。

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

提示

样例 1 解释

一种可行的方案是,删除输入的第 22 条边 (1,3)(1, 3) 和第 66 条边 (3,4)(3, 4)


数据规模与约定

对于全部的测试点,保证 1n50001\leq n\leq 50001m1000001\leq m\leq100000,给定的图没有重边和自环。