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 < 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$). [Image] 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.


-----Input-----

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.


-----Output-----

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


-----Examples-----
Input
5 7
2 4
5 1
2 3
3 4
4 1
5 3
3 5

Output
10 9 10 10 9 

Input
2 3
1 2
1 2
1 2

Output
5 6 



-----Note-----

Consider the second sample.

If the train started at station $1$, the optimal strategy is as follows.  Load the first candy onto the train.  Proceed to station $2$. This step takes $1$ second.  Deliver the first candy.  Proceed to station $1$. This step takes $1$ second.  Load the second candy onto the train.  Proceed to station $2$. This step takes $1$ second.  Deliver the second candy.  Proceed to station $1$. This step takes $1$ second.  Load the third candy onto the train.  Proceed to station $2$. This step takes $1$ second.  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.

Difficulty: competition

Starter code:

Solutions:

import sys
#sys.stdin=open("data.txt")
input=sys.stdin.readline
mii=lambda:list(map(int,input().split()))

n,m=mii()
a=[[] for _ in range(n)]
c=[123456 for _ in range(n)]
for _ in range(m):
    u,v=mii()
    u%=n
    v%=n
    if v<u: v+=n
    a[u].append(v)
    if c[u]>v: c[u]=v

ans=[]
for i in list(range(1,n))+[0]:
    out=0
    for j in range(i,n):
        if not a[j]: continue
        tmp=(j-i)+(len(a[j])-1)*n+(c[j]-j)
        out=max(out,tmp)
        #print(1,i,j,tmp)
    for j in range(i):
        if not a[j]: continue
        tmp=(j+n-i)+(len(a[j])-1)*n+(c[j]-j)
        out=max(out,tmp)
        #print(2,i,j,tmp)
    ans.append(out)
print(" ".join(map(str,ans)))


from collections import defaultdict as dd, deque

n,m = list(map(int,input().split()))

S = dd(list)

for _ in range(m):
    start,dest = list(map(int,input().split()))
    S[start-1].append(dest-1)

closest = [0]*n
for i in range(n):
    if S[i]:
        closest[i] = min((j-i)%n for j in S[i])

R = [0]*n
for start in range(n):
    mx = 0
    for di in range(n):
        i = (start + di)%n
        cost = di + (len(S[i])-1)*n + closest[i]
        mx = max(mx, cost)
    R[start] = mx

print(' '.join([str(x) for x in R]))





n,m=map(int,input().split())
stations=[]
for i in range(n):
    stations.append([])
for i in range(m):
    a,b=map(int,input().split())
    stations[a-1].append((b-a)%n)
maxes=[]
for i in range(n):
    if len(stations[i])>0:
        big=min(stations[i])
    else:
        big=0
    maxes.append(n*max(len(stations[i])-1,0)+big)
out=[]
new=maxes[:]
big=0
for j in range(n):
    if new[j]+j>big and new[j]>0:
        big=new[j]+j
curr=big
out.append(str(curr))
for i in range(n-1):
    if maxes[i]>0:
        curr=max(curr-1,maxes[i]+n-1)
    else:
        curr=curr-1
    out.append(str(curr))
print(" ".join(out))

def dist(a,b):
    return (b-a)%n

n, m = map(int, input().split())

cnd = [0 for x in range(n+1)]
mn = [5000 for x in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    # print(a,b,dist(a,b))
    cnd[a] += 1
    mn[a] = min(mn[a], dist(a,b))
# print(mn)
# print(cnd)

for i in range(1,n+1):
    ans = 0
    for j in range(1,n+1):
        if cnd[j] > 0:
            ans = max(ans, dist(i,j) + n*(cnd[j]-1) + mn[j])
    print(ans, end=" ")


def dista(start, n):
    return lambda end: n - (start - end) if(start > end) else end - start

n, m = list(map(int,input().split(' ')))
dicta = [[] for i in range(n+1)]
for i in range(m):
    s, d = list(map(int,input().split(' ')))
    dicta[s].append(d)
for i in range(n+1):
    dicta[i].sort(key = dista(i, n))
maxlen = max((list(map(len, dicta))))


result = (maxlen-1)*n
minadd = 0

ansans = []
for k in range(1, n+1):
    disk = dista(k, n)
    minadd = 0
    for i in range(1, n+1):
        lndicta = len(dicta[i])
        tmp = 0
        if(lndicta == maxlen-1):
            if lndicta != 0:
                tmp = min([(disk(i) + dista(i, n)(j)) for j in dicta[i]]) - n
        elif(lndicta == maxlen):
            tmp = min([(disk(i) + dista(i, n)(j)) for j in dicta[i]])
        if(tmp > minadd):
            minadd = tmp
    ansans.append(str(minadd + result))

print(' '.join(ansans))


(n, m), count, length = list(map(int, input().split())), {}, {}
for _ in range(m):
	a, b = list(map(int, input().split()))
	count[a] = count[a]+1 if a in count.keys() else 1
	length[a] = min(length[a], (b+n-a) % n) if a in length.keys() else (b+n-a) % n
for i in range(1, n+1):
		print(max((length[j] + j-i + n*(count[j]-(j >= i)) if count[j] != 0 else 0 for j in count.keys())), end=' ')

def __starting_point():
	from sys import stdin
	n, m = list(map(int, stdin.readline().split()))
	c = {}
	for _ in range(m):
		a, b = list(map(int, stdin.readline().split()))
		if (a-1) not in c.keys():
			c[a-1] = []
		x = b-a + (n if b<a else 0)
		c[a-1].append(x)

	for k, l in c.items():
		c[k] = min(l) + ((len(l)-1)*n)

	out_ = []
	for x in range(n):
		res = 0
		for y, v in c.items():
			s = y-x + (n if y<x else 0)
			res = max(res, v+s)
		out_.append(res)

	print(*out_)
__starting_point()

n, m = map(int, input().split())

a = [[] for i in range(5010)]

for i in range(m):
	x, y = map(int, input().split())
	if y < x:
		a[x].append(n - x + y)
	else:
		a[x].append(y - x)


for i in range(1, n + 1):
	a[i].sort()

mx = int(-1e9)

for i in range(1, n + 1):
	if len(a[i]):
		mx = n * (len(a[i]) - 1) + a[i][0]
	else:
		mx = 0
	
	k = 1
	l = i + 1
	if l == n + 1:
		l = 1
	
	while l != i:
		if len(a[l]):
			mx = max(mx, n * (len(a[l]) - 1) + a[l][0] + k)
			
		k += 1
		l += 1
		if l == n + 1:l = 1
	print(mx, end = " ")

print()


#!/usr/bin/env python
# coding: utf-8

# In[21]:


import copy
r = input().split()
n = int(r[0])
m = int(r[1])
ar = [[] for i in range(n)]
#print(ar)
for i in range(m):
   r = input().split()
   a = int(r[0]) 
   b = int(r[1])
   ar[a - 1].append(b - 1)
#   print(ar)
train = []
result = []
for i in range(n):
    count = m
    arr = copy.deepcopy(ar)
    time = copy.deepcopy(ar)
    ind = i
    res = 0
    for j in range(n):
        for k in range(len(arr[j])):
            if arr[j][k] >= j:
                time[j][k] = arr[j][k] - j
            else:
                time[j][k] = n - 1 - j + arr[j][k] + 1
#print(time)                
    while (count != 0) or (len(train) != 0):
        if len(arr[ind]) != 0:
            train.append(arr[ind][time[ind].index(max(time[ind]))])
#        print(time[ind].index(max(time[ind])))
#        print(max(time[ind]))
            del arr[ind][time[ind].index(max(time[ind]))]
            del time[ind][time[ind].index(max(time[ind]))]
#        print(arr)
#        print(time)
            count -= 1
#    print(train)    
        while train.count(ind) != 0:
            train.remove(ind)
#        print(train)
        ind += 1
        if ind == len(arr): 
            ind = 0
        res += 1
    result.append(res - 1)    
#    print(ind)
#    print(res) 
print(' '.join(map(str, result)))
#print(ind)
    


# 

# ## 

# In[ ]:






n,m=list(map(int,input().split()))
ms,md=[n-1 for i in range(n+1)],[-1 for i in range(n+1)]
def distance(sfrom,sto):
    nonlocal n
    return sto-sfrom if sto>=sfrom else sto+n-sfrom 
for i in range(m):
    c,d=list(map(int,input().split()))
    md[c]+=1
    ms[c]=min(distance(c,d),ms[c])
for i in range(1,n+1):
    md[i]=n*md[i]+ms[i]
ans=[]
for i in range(1,n+1):
    ans.append(max([md[k]+distance(i,k)if md[k]>0 else 0 for k in range(1,n+1)]))
print(' '.join([str(i)for i in ans]))
    



def distance(b, a, n):
    return b - a if b >= a else b + n - a


n, m = list(map(int, input().split()))
dic_last_candy = dict()
dict_node = dict()
s = ''
for i in range(m):
    a, b = list(map(int, input().split()))
    c = dict_node.get(a, 0)
    c += 1
    dict_node[a] = c
    last_candy = dic_last_candy.get(a, 0)
    if last_candy:
        c1 = distance(last_candy, a, n)
        c2 = distance(b, a, n)
        if c2 < c1:
            last_candy = b
    else:
        last_candy = b
    dic_last_candy[a] = last_candy

for i in range(1, n + 1):
    c = dict_node.get(i, 0)
    if c:
        now_step = (c - 1) * n + distance(dic_last_candy[i], i, n)
        dict_node[i] = now_step
s = ''
for i in range(1, n + 1):
    now_step = dict_node.get(i, 0)
    min_step = now_step
    for j in range(1, n + 1):
        if dict_node.get(j, 0):
            now_step = dict_node.get(j, 0) + distance(j, i, n)
            if min_step < now_step:
                min_step = now_step
    s += ' ' + str(min_step)
print(s[1:])


def dist(a, b):
    return (b - a) % n

n, m = list(map(int, input().split(" ")))

sweets = {i: [] for i in range(n)}
for i in range(m):
    s, t = list(map(int, input().split(" ")))
    sweets[s - 1].append(t - 1)

t = {i: 0 for i in range(n)}

for i in range(n):
    sweets[i] = sorted(sweets[i], key=lambda x: -dist(i, x))
    if len(sweets[i]):
        t[i] = (len(sweets[i]) - 1) * n + dist(i, sweets[i][-1])

result = []
for s in range(n):
    max_dist = 0
    for i in range(n):
        if t[i] and t[i] + dist(s, i) > max_dist:
            max_dist = t[i] + dist(s, i)
    result.append(max_dist)

print(" ".join(map(str, result)))

import copy

n, m = list(map(int, input().strip().split()))
items = [[] for _ in range(n)]
for _ in range(m):
    u, v = list(map(int, input().strip().split()))
    items[u - 1].append(v - 1)
for i, line in enumerate(items):
    pairs = []
    for v in line:
        pairs.append((v - i, v) if v > i else (n - i + v, v))
    pairs = sorted(pairs, reverse=True)
    items[i] = [pair[1] for pair in pairs]
ans = []
for s in range(n):
    need = m
    items_idx = [0 for _ in range(n)]
    items_cnt = [0 for _ in range(n)]
    items_tot = 0
    ans.append(-1)
    while need > 0 or items_tot > 0:
        idx = s % n
        if items_idx[idx] < len(items[idx]):
            items_cnt[items[idx][items_idx[idx]]] += 1
            items_idx[idx] += 1
            items_tot += 1
            need -= 1
        items_tot -= items_cnt[idx]
        items_cnt[idx] = 0
        s += 1
        ans[-1] += 1
    ans[-1] = max(0, ans[-1])
print(' '.join(map(str, ans)))


def prog():
    n,m = map(int,input().split())
    d = {i:[] for i in range(1,n+1)}
    from sys import stdin
    for i in range(m):
        a,b = map(int,stdin.readline().split())
        d[a].append(b)
    res = []
    for i in range(1,n+1):
        lst=[]
        for j,x in enumerate(d):
            mn,k=100000,-1
            for k,y in enumerate(d[x]):
                if x<y:
                    a=y-x
                else:
                    a=n-x+y
                if a<mn:
                    mn=a
            if k>-1:
                if i<=x:
                    b=x-i
                else:
                    b=n-i+x
                lst.append(k*n+mn+b)
        res.append(max(lst))
    print(*res)
prog()

def distance(fro ,to):
    nonlocal n
    return to - fro if to-fro>=0 else n+to-fro
n , m =  list(map(int,input().split()))
count=[-1 for i in range(n+1)]
dis=[n for i in range(n+1)]
ans=[]
for i in range(1,m+1):
    a , b = list(map(int,input().split()))
    dis[a] = min(distance(a,b),dis[a])
    count[a] +=1
#    print(a,count[a])
#    print(dis[a],a,n,b)
#print(dis)    
for i in range(1,n+1):
    dis[i] = dis[i]+ n*count[i]
#    print(dis[i],count[i],i)
#print(dis) 
for i in range(1,n+1):
    ans.append(max([dis[k]+distance(i,k) if dis[k]>0 else 0 for k in range(1,n+1)]))
print(*ans)    
    
    


def distance(fro ,to):
    nonlocal n
    return to - fro if to-fro>=0 else n+to-fro
n , m =  list(map(int,input().split()))
count=[-1 for i in range(n+1)]
dis=[n for i in range(n+1)]
ans=[]
for i in range(1,m+1):
    a , b = list(map(int,input().split()))
    dis[a] = min(distance(a,b),dis[a])
    count[a] +=1
#    print(a,count[a])
#    print(dis[a],a,n,b)
for i in range(1,n+1):
    dis[i] = dis[i]+ n*count[i]
#    print(dis[i],count[i],i)
#print(dis) 
for i in range(1,n+1):
    ans.append(max([dis[k]+distance(i,k) if dis[k]>0 else 0 for k in range(1,n+1)]))
print(*ans)    
    
    


N, m = [int(value) for value in input().split()]

candies = []
for _ in range(N):
    candies.append([])

for _ in range(m):
    start, end = [int(value) for value in input().split()]
    candies[start - 1].append(end - 1)

min_distantions = []

for start_pos in range(N):
    min_distantion = 0

    for shift in range(N):
        current_pos = (start_pos + shift) % N
        count_candies = len(candies[current_pos])

        if count_candies > 0:
            closest_candy = N - 1
            for candy_destination in candies[current_pos]:
                closest_candy = min(closest_candy,
                                    (N + candy_destination - current_pos) % N)

            min_distantion = max(min_distantion, closest_candy +
                                 shift + N * (count_candies - 1))

    min_distantions.append(min_distantion)

print(' '.join([str(distantion) for distantion in min_distantions]))


import sys
from collections import defaultdict,deque
n,m=list(map(int,sys.stdin.readline().split()))
dist=defaultdict(list)
sweet=defaultdict(list)
for i in range(m):
    u,v=list(map(int,sys.stdin.readline().split()))
    sweet[u].append(v)
    dist[u].append(0)
for i in sweet:
    le=len(sweet[i])
    for j in range(le):
        if sweet[i][j]>=i:
            dist[i][j]=sweet[i][j]-i
        else:
            dist[i][j]=n-(i-sweet[i][j])
    dist[i].sort()
#print(dist,'dits')
for i in dist:
    count=0
    le=len(dist[i])
    for k in range(le-1,-1,-1):
        dist[i][k]+=count*n
        count+=1
    dist[i].sort()
vis=defaultdict(int)
for i in dist:
    if dist[i]==[]:
        vis[i]=0
    else:
        vis[i]=dist[i][-1]
#print(dist,'dist')
#print(vis,'vis')
ans=[0 for _ in range(n)]
for i in range(1,n+1):
    cur=0
    #print(i,'i')
    for k in range(1,n+1):
        new=0
        if k>=i:
            if vis[k]!=0:
                new=vis[k]+k-i
                #print(new,'new',k,'k')
        else:
            if vis[k]!=0:
                new=vis[k]+(n)-(i-k)
                #print(new,'new',k,'k')
        cur=max(cur,new)
    ans[i-1]=cur
print(*ans)