首先注意到在不进行修改的情况下，我们可以把原图分成若干个强联通分量，从一个点出发能到的最多的满足条件的城市数量就是它所在强联通分量的大小（这个思路非常典了吧）。
所以开始先缩一遍点，然后建好新图。
接下来该怎么办啊？注意到新增航线只能是现有航线的回程，而 m 不大，可以想到枚举所有的原有边，看看建反向边之后会发生那些影响。
如果我们枚举到的边的起点所在的分量是 u ，终点所在的是 v ，那么如果我们从 v 向 u 连边的话：
-
如果 u=v ，即本来就处于一个分量之中，没有任何影响。
-
否则，显然 u 、 v 会合并成一个更大的强连通分量，但是仅仅只有这些吗？考虑一个区间 i ，如果能从 u 到 i 再到 v 的话，连边之后显然 i 也会属于这个新的强联通分量。
问题解决，我们只需要建完新图之后对每个点（每个强联通分量）进行一遍 dfs，统计它可以到达哪些点，最后 m 的循环里面 \Theta(n) 枚举所有分量进行上述操作即可。可以通过本题。
#include <bits/stdc++.h>
#define f(i ,m ,n ,x) for (int i = (m) ;i <= (n) ;i += (x))
using namespace std ;
template < typename T > inline void read ( T &x ) {
x = 0 ;
bool flag (0) ;
register char ch = getchar () ;
while (! isdigit (ch)) {
flag = ch == '-' ;
ch = getchar () ;
}
while (isdigit (ch)) {
x = (x << 1) + (x << 3) + (ch ^ 48) ;
ch = getchar () ;
}
flag ? x = - x : 0 ;
}
template < typename T,typename ...Args >
inline void read ( T &x ,Args &...tmp ) {
read (x) ,read (tmp...) ;
}
const int N = 4e4 + 7 ;
int n ,m ,ohead[N << 1] ,otot ,head[N << 1] ,tot ,u[N] ,v[N] ;
int dfn[N] ,low[N] ,dcnt ,ccnt ,scc[N] ,stk[N] ,stop ,siz[N] ,ans[N] ;
vector < int > num ;
bool instk[N] ,arr[2007][2007] ;
struct edge {
int to ,nxt ;
} oe[N << 1] ,e[N << 1] ;
namespace melo {
inline void oadd (int u ,int v) {
oe[++ otot].nxt = ohead[u] ;
ohead[u] = otot ;
oe[otot].to = v ;
}
inline void add (int u ,int v) {
e[++ tot].nxt = head[u] ;
head[u] = tot ;
e[tot].to = v ;
}
inline void tarjan (int cur) {
dfn[cur] = low[cur] = ++ dcnt ;
stk[++ stop] = cur ;
instk[cur] = true ;
for (int i = ohead[cur] ;i ;i = oe[i].nxt) {
int nex = oe[i].to ;
if (! dfn[nex]) {
melo :: tarjan (nex) ;
low[cur] = min (low[cur] ,low[nex]) ;
} else if (instk[nex])
low[cur] = min (low[cur] ,dfn[nex]) ;
}
if (low[cur] == dfn[cur]) {
ccnt ++ ;
int tmp ;
do {
tmp = stk[stop --] ;
instk[tmp] = false ;
siz[ccnt] ++ ;
scc[tmp] = ccnt ;
} while (tmp != cur) ;
}
}
inline void dfs (int cur ,bool arr[]) {
arr[cur] = true ;
for (int i = head[cur] ;i ;i = e[i].nxt) {
int nex = e[i].to ;
if (arr[nex])
continue ;
melo :: dfs (nex ,arr) ;
}
}
}
int main () {
freopen ("travel.in" ,"r" ,stdin) ;
freopen ("travel.out" ,"w" ,stdout) ;
read (n ,m) ;
f (i ,1 ,m ,1) {
read (u[i] ,v[i]) ;
melo :: oadd (u[i] ,v[i]) ;
}
if (m == 0) {
puts ("1") ;
return puts ("0") ,0 ;
}
f (i ,1 ,n ,1) {
if (! dfn[i])
melo :: tarjan (i) ;
}
f (i ,1 ,m ,1) {
int uu = scc[u[i]] ,vv = scc[v[i]] ;
if (uu == vv)
continue ;
melo :: add (uu ,vv) ;
}
int cur = *max_element (siz + 1 ,siz + ccnt + 1) ;
f (i ,1 ,ccnt ,1)
melo :: dfs (i ,arr[i]) ;
int mx = cur ;
f (i ,1 ,m ,1) {
int uu = scc[u[i]] ,vv = scc[v[i]] ;
int res = 0 ;
f (i ,1 ,ccnt ,1)
res += (arr[uu][i] & arr[i][vv]) * siz[i] ;
ans[i] = max (res ,cur) ;
}
int anss = *max_element (ans + 1 ,ans + m + 1) ;
cout << anss << '\n' ;
f (i ,1 ,m ,1) {
if (ans[i] == anss)
num.emplace_back (i) ;
}
cout << num.size () << '\n' ;
for (auto i : num)
cout << i << ' ' ;
puts ("") ;
return 0 ;
}