8304: BZOJ4304:道路改建

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

人称不死将军的林登•万,与他的兄弟林登•图两人的足迹踏遍了地球的每一寸土地。他们曾将战火燃遍了世界。即使是lifei888这样的强悍人物也从来没有将他彻底击败。 这一次,林登•万在N个城市做好了暴动的策划。然而,在起事的前一天,将军得知计划已经泄漏,决定更改计划,集中力量掌握一部分城市。 具体来说,有M条单向边连接着这N座城市。对于两座城市A,B,如果它们能够通过单向边直接或间接的互相到达,那么就林登•万可以同时控制A,B两座城市而不至于分散力量,反之则会被lifei888各个击破。 为了扩大成果,将军还组织了人手改建道路。这些人可以在起事前将其中一条有向边改变成双向边(注意只能改建其中一条单向边,另外M-1条单向边保持不变),现在,将军想要知道他通过改建其中一条单向边最多能控制几座城市,以及被改建的这一条单向边有多少种选择方案。


输入格式

第一行为两个正整数N,M。 接下来M行每行两个范围在1~N内的正整数x,y,表示有一条从x到y的单向边。 输入保证任意两点的任意方向最多只有一条边直接相连。


输出格式

输出共三行。 第一行一个正整数,将军最多能控制的城市数量。 第二行一个正整数L,表示有L种改建方案使得将军能控制最多的城市。 第三行L个按递增顺序给出的正整数ki,表示改建输入中的第ki条有向边能使将军能控制最多的城市。


样例输入

5 4
1 2
2 3
1 3
4 1

样例输出

3
1
3

提示

对于100%的数据,N<=2000 M<=N*N


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: