[SGU525] Revolutionary Roads / 革命之路

题目描述

Berland 有 $n$ 个城市和 $m$ 条单向道路。城市编号为 $1\sim n$，道路按照输入顺序编号为 $1\sim m$。任意两个城市之间的同一方向至多有一条道路。

定义一个城市集合是互相可达的，当且仅当集合中任意一个城市都能沿道路到达集合中的任意另一个城市。一个国家道路系统的“发展度”定义为最大的互相可达城市集合的大小，也就是有向图中最大强连通分量的大小。

政府最多可以选择一条现有的单向道路，将它改造成双向道路。设经过最优选择后能够达到的最大发展度为 $w$。

如果把第 $i$ 条道路改为双向道路后，道路系统的发展度恰好等于 $w$，则称第 $i$ 条道路为一条革命之路。

请计算 $w$，并找出所有革命之路。

输入格式

第一行两个整数 $n,m$，分别表示城市数和道路数。

接下来 $m$ 行，每行两个整数 $a_i,b_i$，表示一条从 $a_i$ 指向 $b_i$ 的单向道路。

保证 $a_i\ne b_i$，且任意两个城市之间同一方向至多存在一条道路。

输出格式

第一行输出一个整数 $w$，表示能够达到的最大发展度。

第二行输出一个整数 $t$，表示革命之路的数量。

第三行按编号从小到大输出这 $t$ 条道路的编号。如果 $t=0$，第三行可以为空。

数据范围

$1\le n\le1000$，$0\le m\le20000$。

样例 1

样例输入

5 4
1 2
2 3
1 3
4 1

样例输出

3
1
3

样例 2

样例输入

3 4
1 2
2 1
1 3
3 1

样例输出

3
4
1 2 3 4