Toy Train

题意翻译

Alice有一套玩具火车,其中包含n个站台和1辆火车.其中,n个站台依次首尾相接,也就是1->2->...->n-1->n->1排列,如下图所示(对应样例1).若火车正处于i号站台(1≤i<n),则可以前往i+1号站台;若火车处于n号站台,则可以前往1号站台。 现在有m个糖果需要Alice搬运.对于第i个糖果,游戏开始前它处于第ai个站台,它应该被运到第bi个站台。 这辆火车可以装载无限多的糖果,且可以在任意站台装载至多1颗糖果,同时卸下任意多的糖果。 火车最初位于k号站台,试问至少经过几个站台(不包括起始站)才能使每颗糖果到达正确的位置。 输入 第一行包括两个整数n,m(2≤n≤5,000,1≤m≤20,000),表示站台个数和糖果个数 。 接下来有m行,每行描述一颗糖果,即ai,bi(ai≠bi)。 输出 一行,包含n个整数,第i个整数表示当k=i时的结果 。 样例2说明 当k=1时,按照如下方式进行 1. 载入糖果1 2. 到达站台2 1 3. 卸下糖果1 4. 到达站台1 2 5. 载入糖果2 6. 到达站台2 3 7. 卸下糖果2 8. 到达站台1 4 9. 载入糖果3 10. 到达站台2 5 11. 卸下糖果3 共经过5个站台 。 当k=2时,火车必须先到达站台1才能载入糖果,因此答案为5+1=6

题目描述

Alice received a set of Toy Train™ from Bob. It consists of one train and a connected railway network of $ n $ stations, enumerated from $ 1 $ through $ n $ . The train occupies one station at a time and travels around the network of stations in a circular manner. More precisely, the immediate station that the train will visit after station $ i $ is station $ i+1 $ if $ 1 \leq i < n $ or station $ 1 $ if $ i = n $ . It takes the train $ 1 $ second to travel to its next station as described. Bob gave Alice a fun task before he left: to deliver $ m $ candies that are initially at some stations to their independent destinations using the train. The candies are enumerated from $ 1 $ through $ m $ . Candy $ i $ ( $ 1 \leq i \leq m $ ), now at station $ a_i $ , should be delivered to station $ b_i $ ( $ a_i \neq b_i $ ). The blue numbers on the candies correspond to $ b_i $ values. The image corresponds to the $ 1 $ -st example.The train has infinite capacity, and it is possible to load off any number of candies at a station. However, only at most one candy can be loaded from a station onto the train before it leaves the station. You can choose any candy at this station. The time it takes to move the candies is negligible. Now, Alice wonders how much time is needed for the train to deliver all candies. Your task is to find, for each station, the minimum time the train would need to deliver all the candies were it to start from there.

输入输出格式

输入格式

The first line contains two space-separated integers $ n $ and $ m $ ( $ 2 \leq n \leq 5\,000 $ ; $ 1 \leq m \leq 20\,000 $ ) — the number of stations and the number of candies, respectively. The $ i $ -th of the following $ m $ lines contains two space-separated integers $ a_i $ and $ b_i $ ( $ 1 \leq a_i, b_i \leq n $ ; $ a_i \neq b_i $ ) — the station that initially contains candy $ i $ and the destination station of the candy, respectively.

输出格式

In the first and only line, print $ n $ space-separated integers, the $ i $ -th of which is the minimum time, in seconds, the train would need to deliver all the candies were it to start from station $ 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 

说明

Consider the second sample. If the train started at station $ 1 $ , the optimal strategy is as follows. 1. Load the first candy onto the train. 2. Proceed to station $ 2 $ . This step takes $ 1 $ second. 3. Deliver the first candy. 4. Proceed to station $ 1 $ . This step takes $ 1 $ second. 5. Load the second candy onto the train. 6. Proceed to station $ 2 $ . This step takes $ 1 $ second. 7. Deliver the second candy. 8. Proceed to station $ 1 $ . This step takes $ 1 $ second. 9. Load the third candy onto the train. 10. Proceed to station $ 2 $ . This step takes $ 1 $ second. 11. Deliver the third candy. Hence, the train needs $ 5 $ seconds to complete the tasks. If the train were to start at station $ 2 $ , however, it would need to move to station $ 1 $ before it could load the first candy, which would take one additional second. Thus, the answer in this scenario is $ 5+1 = 6 $ seconds.