CF1129A1.Toy Train (Simplified)

This is a simplified version of the task Toy Train. These two versions differ only in the constraints. Hacks for this version are disabled.

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 \lt 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.

这是题目《玩具火车》的一个简化版本。这两个版本仅在约束条件上有所不同。本版本禁止使用 Hack 数据。

Alice 从 Bob 那里收到了一套 Toy Train™ 玩具。它包含一列火车和一个由 $n$ 个车站组成的连通铁路网络，车站编号为 $1$ 到 $n$。火车在任意时刻恰好占据一个车站，并沿车站网络以环形方式运行。更准确地说：若当前位于车站 $i$，则下一时刻将到达的车站为——当 $1 \leq i < n$ 时为车站 $i+1$；当 $i = n$ 时为车站 $1$。按上述规则，火车行驶至下一个车站耗时 $1$ 秒。

Bob 在离开前给了 Alice 一项有趣的任务：利用这列火车，将初始位于某些车站的 $m$ 颗糖果运送到各自独立的目的地。糖果编号为 $1$ 至 $m$。其中，第 $i$ 颗糖果（$1 \leq i \leq m$）当前位于车站 $a_i$，需被运送到车站 $b_i$（满足 $a_i \neq b_i$）。

图中糖果上的蓝色数字对应各 $b_i$ 值。该图对应第一个样例。

火车容量无限，且可在任意车站卸下任意数量的糖果。但火车在离开一个车站前，最多只能从该车站装载一颗糖果（可任选其中一颗）。移动糖果本身所耗时间可忽略不计。

现在，Alice 想知道：火车完成所有糖果运送所需的最短时间是多少？你的任务是：对每个车站，计算若火车从该车站出发，完成全部运送任务所需的最少时间。

The first line contains two space-separated integers $n$ and $m$ ($2 \leq n \leq 100$; $1 \leq m \leq 200$) — 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.

第一行包含两个用空格分隔的整数 $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$ 的初始所在车站和该糖果的目的地车站。

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$.

在第一行且唯一的一行中，输出 $n$ 个用空格分隔的整数，其中第 $i$ 个整数表示火车从第 $i$ 号车站出发，将所有糖果送达所需的最短时间（单位：秒）。

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.

考虑第二个样例。

如果列车从第 $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$ 号车站才能装载第一颗糖果，这将额外增加 $1$ 秒。因此，此情形下的答案为 $5+1 = 6$ 秒。