问题陈述
JAG王国是一个奇怪的王国,其$N$城市仅通过单向道路连接。 $N$ 城市编号为 $1$ 到 $N$。 ICPC(国际特色产品公司)每天将其产品从$S$市的工厂运输到JAG王国$T$市的仓库。 为了提高效率,ICPC 同时使用多辆卡车。 每辆卡车从 $S$ 出发,在单向公路网络上到达 $T$,途经一些城市(或直接)。 为了减少交通堵塞和事故的风险,没有两辆卡车走同一条道路。
现在,ICPC希望提高日常运输的效率,而ICPC在上述约束下,使用尽可能多的卡车进行日常运输。 财政受到ICPC严重影响的JAG Kingdom考虑改变单向道路的方向,以增加ICPC日常运输的卡车数量。 由于多条道路反转会造成混乱,JAG Kingdom 决定最多反转一条道路。
如果没有道路可以通过逆转道路来提高运输效率,JAG王国不需要逆转任何道路。 检查单条道路的逆转是否可以提高当前日常运输的卡车最大数量。 如果是,则计算当单向道路可以倒车时,最多可以有多少辆卡车走不相交的道路组,以及可以选择多少条道路作为要倒车的道路,以实现最大。
输入
输入由多个数据集组成。数据集数量不超过100美元。
每个数据集的格式如下。
$N$ $M$ $S$ $T$
$a_1$ $b_1$
$a_2$ $b_2$
:
:
$a_M$ $b_M$
每个数据集的第一行包含四个整数: 城市数量 $N$ ($2 \le N \le 1{,}000$),道路数量 $M$ ($1 \le M \le 10{,}000$),有工厂的城市 $S$ 和有仓库的城市 $T$ ($1 \le S, T \le N$, $S \neq T$)。
下面的$M$行描述了道路的信息。 其中第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le N$, $a_i \neq b_i$),表示第 $i$ 条路是从 $a_i$ 到 $b_i$。
输入结束由包含四个零的行表示。
输出
对于每个数据集,输出一行中用一个空格分隔的两个整数,如下所示: 如果单条道路的反转提高了当前每日运输的最大卡车数量,则第一个输出整数是一条道路反转后的新的最大值,第二个输出整数是可以选择作为要反转的道路以实现新的最大值的道路数量。 否则,即如果当前最大值不能通过任何道路反转而增加,则第一个输出整数是当前最大值,第二个输出整数是 $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