题目描述

cxm 最近在玩一个叫做猴子挖矿的游戏。

这个游戏由两个玩家参加。开始时地图中会随机生成一些矿点，玩家需要操作自己的猴子探索未知的道路，抢占对方的矿点。已经占领的矿点每回合会产生 $1$ 单位的矿石。玩家用手中的矿石可以购买路灯、护盾、传送等道具。最终获得矿石较多的玩家获胜。

cxm 对这个游戏进行了一些改动。现在游戏在一个有 $n$ 个点，$m$ 条边的有向图上进行，为了方便起见，cxm 用 $1$ 到 $n$ 的整数来表示地图中的点。

玩家只有一个，但他拥有无限数量的猴子。游戏最开始时，所有的猴子都在第 $1$ 个点。每一回合，所有的猴子必须沿着图中的一条有向边移动到下一个点。玩家可以给不同的猴子指定不同的路线，但不能让猴子呆在原地不动。无路可走的猴子会在下一回合消失。

游戏开始时为第 $0$ 回合。从第 $s$ 回合开始，到第 $t$ 回合结束（包括第 $s$ 回合和 $t$ 回合），每回合每个点都会出产 $1$ 单位的矿石。如果在该回合玩家有至少一只猴子在出产矿石的点，那么玩家将获得这个矿石，否则这个矿石会在下一回合消失。

现在 cxm 想知道，在图中的每个点他分别最多可以获得多少个矿石。

输入格式

标准输入。

输入第一行包含四个正整数 $n,m,s,t$，分别表示有向图中点的个数，边的个数，开始出产的时间和结束出产的时间。
接下来 $m$ 行，每行包含两个 $1$ 到 $n$ 的整数 $x,y$，用空格隔开，表示有一条从第 $x$ 个点到第 $y$ 个点的有向边。

输出格式

标准输出。

输出 $n$ 行，每行包含一个整数，按照 $1$ 到 $n$ 的顺序依次表示在每个点可以获得的矿石个数。

5 7 0 19
1 3
1 4
1 5
3 2
2 1
3 4
5 5

7
6
7
13
19

数据规模与约定

对于 $100\%$ 的数据，保证 $0<n\le 100$，$0<m\le 300$，$0\le s\le t\le 10^{15}$。

样例解释

题目来源

By 佚名提供