问题描述:
有一个新开的水上乐园,业主准备用它最大的景点“滑梯的天堂”作为宣传来吸引顾客。
这是一个巨大的水滑梯网络,覆盖整个山腰。每个滑道的的末端都有一个平台,通常与至少一个其他滑道的起点相连,可以进一步下滑(有些不是,那些所谓的侧出口为客人提供了提前离开景点的可能性)。客人从顶部平台开始,通过众多滑道序列中的一个,一路下滑到底层平台(或其中一个侧出口)
由于他们认为顾客一般从顶层平台滑到底层平台的可能性最大,所以业主想在广告中使用这个数字,你可以帮他们计算一下吗?
输入:
- 一行包括N,M,s和t (2 ≤ N ≤ 5 · 10^4, 0 ≤ M ≤ 2 · 10^5,1 ≤ s, t ≤ N) 分别代表平台的数量,滑道的数量,顶部平台和底层平台的指数
- M行用来描述滑道,第i行包括整数$b_i$和$e_i$ (1 ≤ $b_i$, $e_i$ ≤ N, bi≠ei) 表示一个滑道从平台$b_i$开始,到平台$e_i$结束。
It is guaranteed that no slides end in the top platform s or start in the bottom platform t and that one can’t get to a platform one has already slid down from without leaving the attraction in the meantime.
输出:
输出上面指定的可能性的数量,结果不超过10^16.
input | output |
---|---|
4 5 1 4 | 3 |
1 2 | - |
2 3 | - |
1 4 | - |
2 4 | - |
3 4 | - |
------ | ------ |
7 8 1 7 | 4 |
1 2 | - |
1 3 | - |
2 4 | - |
3 4 | - |
4 5 | - |
4 6 | - |
5 7 | - |
6 7 | - |
------ | ------ |
5 7 1 5 | 5 |
1 2 | - |
1 3 | - |
1 4 | - |
2 3 | - |
3 4 | - |
3 5 | - |
4 5 | - |