A116498.道路规划（road）

【题目背景】

小A所在的岛上一共有$n$座城市，城市之间一共有$m$条单向道路连接。保证这些道路不会形成环路，也就是不存在从某座城市出发，经过一系列的道路最终又回到原点的情形。

出于某种原因，小A需要从起点城市$s$前往城市$t$，可能会有许多种不同的路径。小A想知道途径的可能的城市（除$s,t$外）中，哪一个城市对他是最重要的，换句话说，从$s$到$t$的所有路径中，需要经过哪个城市的路径条数最多。

【题目描述】

给定一个$n$个点$m$条边的有向无环图，所有点的编号从$1$到$n$，给出一个起点$s$和一个终点$t$，求出一个点$ans$，使得经过$ans$的从$s$到$t$的路径条数最多。

输出这个点$ans$和具体的路径数，如果有多个点经过的数相同，取编号最小的那个；如果$s$不能到达$t$，或从$s$到$t$的路径中不可能途经其他点，输出$-1$。

输入的第一行包含4个整数，分别为$n,m,s,t$。表示点数、边数、起点和终点。

接下来$m$行，每行2个整数$u,v$，表示存在一条从$u$到$v$的有向路径。

输出仅1行。如果$s$不可达，或中间不能途经其他点，输出$-1$；否则输出两个数字，表示最重要的点的编号和经过它的路径条数。

【样例解释】

样例图如下，起点是 $1$，终点是 $5$：

经过 $2$ 的路径最多，一共有 $4$ 条：

$\{1,2,3,5\},\{1,2,4,5\},\{1,2,5\},\{1,2,3,4,5\}$。所有从 1 出发到达 5 的路径中，经过其他点的路径均小于 4。比如，经过 3 的路径只有 3 条$\{1,2,3,5\},\{1,3,5\},\{1,3,4,5\}$。

【数据范围】

对于所有测试数据保证：$1\leq n\leq10^4,1\leq m\leq5\times10^5$，保证不会出现重边和自环。保证$s$到$t$的路径条数不超过$2^{63}-1$。

测试点	$n\leq$	$m\leq$	特殊性质
1~2	10	30	无
3~4	15	45	无
5	$10^2$	$3\times10^2$	A
6~7	$10^2$	$3\times10^2$	无
8~9	60	$3\times10^3$	C
10	$10^3$	$3\times10^3$	B
11~13	$10^3$	$5\times10^3$	无
14~15	$10^4$	$5\times10^4$	无
16	$10^4$	$5\times10^5$	B
17~20	$10^4$	$5\times10^5$	无

特殊性质A：保证有且仅有一个点入度为0、出度为1；有且仅有一个点入度为1、出度为0，其余所有点入度出度均为1。

特殊性质B：除起点$s$和终点$t$外，所有点的出度和入度均为1。

特殊性质C：$m=\frac{n(n-1)}{2}$。