这是任务玩具火车的简化版本。这两个版本仅在约束方面有所不同。此版本的黑客功能已被禁用。
Alice 从 Bob 那里收到了一套玩具火车™。它由一列火车和一个由 $$$n$$$ 站组成的连接铁路网络组成,从 $$$1$$$ 到 $$$n$$$ 列举。火车一次只占用一个车站,并以循环方式绕车站网络行驶。更准确地说,如果 $$$1 \leq i < n$$$,火车在车站 $$$i$$$ 之后将访问的直接车站是车站 $$$i+1$$$,或者如果 $$$i = n$$$,车站是 $$$1$$$。如所述,火车需要 $$$1$$$ 秒才能到达下一站。
鲍勃在离开前给了爱丽丝一项有趣的任务:使用火车将最初在某些车站的 $$$m$$$ 糖果运送到各自独立的目的地。糖果从 $$$1$$$ 到 $$$m$$$ 进行计数。糖果$$$i$$$ ($$$1 \leq i \leq m$$$),现在在车站$$$a_i$$$,应该被送到车站$$$b_i$$$ ($$$a_i \neq b_i$$$)。
糖果上的蓝色数字对应于 $$$b_i$$$ 值。该图像对应于 $$$1$$$-st 示例。
火车的容量是无限的,并且可以在车站装载任意数量的糖果。然而,在火车离开车站之前,一个车站最多只能装载一颗糖果到火车上。你可以在这个站选择任何糖果。移动糖果所需的时间可以忽略不计。
现在,爱丽丝想知道火车需要多少时间才能运送所有糖果。你的任务是找到每个车站,如果火车从那里出发,运送所有糖果所需的最短时间。
输入
第一行包含两个空格分隔的整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 100$$$; $$$1 \leq m \leq 200$$$) — 分别是车站数量和糖果数量。
以下 $$$m$$$ 行中的第 $$$i$$$ 行包含两个空格分隔的整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$; $$$a_i \neq b_i$$$) — 最初包含糖果 $$$i$$$ 的车站和目的地分别是糖果站。
输出
在第一行也是唯一一行中,打印 $$$n$$$ 以空格分隔的整数,其中 $$$i$$$ 是火车从 $$$i$$$ 车站出发所需的最短时间(以秒为单位)。
示例
输入 #1
5 7 2 4 5 1 2 3 3 4 4 1 5 3 3 5
输出 #1
10 9 10 10 9
输入 #2
2 3 1 2 1 2 1 2
输出 #2
5 6
注意
考虑第二个示例。
如果火车从$$$1$$$车站出发,则最优策略如下。
1. 将第一块糖果装载到火车上。
2. 前往$$$2$$$站。此步骤需要 $$$1$$$ 秒。
3. 交付第一颗糖果。
4. 前往$$$1$$$站。此步骤需要 $$$1$$$ 秒。
5. 将第二颗糖果装载到火车上。
6. 前往$$$2$$$站。此步骤需要 $$$1$$$ 秒。
7. 交付第二颗糖果。
8. 前往$$$1$$$站。此步骤需要 $$$1$$$ 秒。
9. 将第三颗糖果装载到火车上。
10. 前往$$$2$$$站。此步骤需要 $$$1$$$ 秒。
11. 交付第三颗糖果。
因此,火车需要 $$$5$$$ 秒才能完成任务。
然而,如果火车从 $$$2$$$ 站出发,则需要移动到 $$$1$$$ 站才能装载第一颗糖果,这将需要额外的时间。因此,这种情况下的答案是 $$$5+1 = 6$$$ 秒。