AT_icpc2014autumn_f Reverse a Road II
题目描述
反转道路2
某个陌生的国度JAG中有N座城市，城市之间用M条单向道路连接。N座城市的编号为1~N。在这个王国里面，每一天ICPC（某国际特色产品的公司）将其产品从市S中的工厂到城市T的仓库。为了提高效率，每一次运输会使用多个卡车。一辆卡车通过单向道路网络从 s通过一些城市（直接或间接）到达T。为了减少交通拥堵以及发生交通事故的风险，没有卡车会走同样的路。
现在，ICPC想提高日常运输的效率，它想在在上面的条件的约束下派出尽可能多的卡车。JAG国，这个财政状况受ICPC影响的国家，认为改变为单向道路的方向可以使ICPC每天派出的卡车数量增加。但因为逆转太多道路会造成混乱，JAG国决定只反转一条单向道路。
如果没有路反转后使运输效率提高，JAG国可以不反转任何道路。你需要检查反转一条道路是否可以提高每天派出卡车的数量。如果是这样的话，计算ICPC公司最多能派出多少辆卡车，以及为了达到这个最大值有多少种方案。
输入格式
有多组输入，组数小于等于100。
第1行有四个整数N,M,S,T（2≤N≤1000，1≤M≤10000，1≤S，T≤N，S≠T），意思如题。
接下来M行，每行两个整数ai,bi（1≤ai，bi，≤N，a1≠bi）表示有一条道路从ai到bi。
输出以四个0结尾。
输出格式
对于每组数据，输出两个被空格隔开的整数：如果改变多条单向道路的方向能增大每日卡车的派出量，则第一个整数为反转道路后的最大派出量，第二个整数为方案数。若没有，则第一个整数为当前的最大派出量，第二个整数为0。
样例输入：
```
4 4 1 4
1 2
3 1
4 2
3 4
7 8 1 7
1 2
1 3
2 4
3 4
4 5
4 6
5 7
7 6
6 4 5 2
1 2
1 3
4 5
5 6
10 21 9 10
9 1
9 2
9 3
9 4
10 1
10 2
10 3
10 4
1 5
2 5
2 6
3 6
3 7
4 7
4 8
1 8
5 10
6 10
7 10
10 8
10 9
2 15 1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
0 0 0 0
```
样例输出：
```
1 2
2 1
0 0
4 6
15 0
```
感谢@zhenglier 提供的翻译