Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

N, M = map(int, input().split())
war_pairs = []
for _ in range(M):
    a, b = map(int, input().split())
    war_pairs.append((a, b))

# 取り除く橋についてbit全探索
bridge_cnt = N - 1
for i in range(2 ** bridge_cnt):

    bridges = [True] * bridge_cnt
    for j in range(bridge_cnt):
        if (i >> j) & 1:
            bridges[bridge_cnt - 1 - j] = False

    # war_pairs間でたどり着けないか確認
    is_unreachable_all = True
    for (a, b) in war_pairs:
        bridges_between_ab = bridges[a - 1:b - 1]
        if all(bridges_between_ab):
            is_unreachable_all = False

    if is_unreachable_all:
        print(bridges.count(False))
        exit()


### FIXED CODE ###

N, M = map(int, input().split())
pairs = []
for _ in range(M):
    i, j = map(int, input().split())
    pairs.append([i, j])

pairs.sort(key=lambda x: x[1])  # 終端が早い順に並び替え

# 重複区間除去(greedy)
current = 0
bag = []
for pair in pairs:
    if pair[0] >= current:
        bag.append(pair)
        current = pair[1]

print(len(bag))
### BUGGY CODE ###

x=input()
i=4
n=len(x)
while i>=0 and n>0:
  x=x.replace('S'*10**i+'T'*10**i,'')
  if n==len(x):
    i-=1
  n=len(x)
print(len(x))

### FIXED CODE ###

#import re
x=input()
ans=0
ns=0
nt=0
for i in range(len(x)):
  if x[i]=='S':
    ns+=1
  elif ns>0 and x[i]=='T':
    ns-=1
  else:
    ans+=1
print(ans+ns)
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
A=[S[0:i+1].count("AC") for i in range(N)]
for i in range(Q):
  l,r=map(int,input().split())
  print(A[r-1]-A[l-1])

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
A=[0]
res=0
for i in range(N):
  if i !=0:
    if S[i-1]=="A" and S[i]=="C":
      res+=1
      A.append(res)
    else:
      A.append(res)
for i in range(Q):
  l,r=map(int,input().split())
  print(A[r-1]-A[l-1])
### BUGGY CODE ###

N, M = map(int, input().split())
aLst = list(map(int, input().split()))
for i in range(M):
    B, C = map(int, input().split())
    for i in range(B):
        aLst.append(C)

aLst.sort(reverse=True)
ans = 0

for i in range(N):
    ans += aLst[i]

print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
aLst = list(map(int, input().split()))
aLst.sort()
cdict = {}
for i in range(M):
    B, C = map(int, input().split())
    if C in cdict.keys():
        cdict[C] = cdict[C] + B
    else:
        cdict[C] = B

for i in aLst:
    if i in cdict.keys():
        cdict[i] = cdict[i] + 1
    else:
        cdict[i] = 1

sordC = sorted(cdict.items(), key=lambda x:x[0], reverse=True)
ans = 0
tmp = 0
for i in range(N):
    for j in range(sordC[i][1]):
        if tmp < N:
            ans += sordC[i][0]
            tmp += 1
        else:
            break
    if tmp >= N:
        break
print(ans)
### BUGGY CODE ###

N=int(input())
A= list(map(int,input().split()))
ans=0
for i in range(N):
    S=sum(A[i+1:])
    ans+=A[i]*S
print(ans%(10**9+7))

### FIXED CODE ###

N=int(input())
A= list(map(int,input().split()))
ans=0
S=sum(A)
for i in range(N):
    S-=A[i]
    ans+=A[i]*S
print(ans%(10**9+7))
### BUGGY CODE ###

def solve():
    N = int(raw_input())
    D = [int(raw_input()) for i in range(N)]
    if sum(D) % 2 > 0:
        print '-1'
        return
    Di = sorted([(di, i) for i, di in enumerate(D)], key = lambda x : x[0], reverse = True)
    d_to_i = {dd:i for dd, i in Di}
    ans = []
    n_child = [1] * N
    d_child = [0] * N
    for valD, node in Di:
        valD_par = valD - N + 2 * n_child[node]
        if valD_par in d_to_i.keys():
            node_par = d_to_i[valD_par]
            ans.append((node_par + 1, node + 1))
            n_child[node_par] += n_child[node]
            d_child[node_par] += n_child[node] + d_child[node]
            if n_child[node_par] == N:
                break
        else:
            print '-1'
            return
    # check if Di satisfied or not
    d_min, i_min = Di[-1]
    if d_child[i_min] != d_min:
        print '-1'
        return
    for i,j in ans:
        print str(i) + ' ' + str(j)

if __name__ == '__main__':
    solve()


### FIXED CODE ###

n = int(input())
d = [int(input()) for i in range(n)]

if sum(d)%2 > 0:
    print(-1)
    exit()

d = sorted([(dd, i) for i, dd in enumerate(d)], reverse = True)
d_to_i = {dd:i for dd, i in d}
n_child = [1]*n
d_child = [0]*n
ans = []
for dd, i in d:
    d_i = dd+2*n_child[i]-n
    if d_i in d_to_i.keys():
        i_next = d_to_i[d_i]
        ans.append((i+1, i_next+1))
        n_child[i_next] += n_child[i]
        d_child[i_next] += d_child[i] + n_child[i]
        if n_child[i_next] == n:
            break
    else:
        print(-1)
        exit()

d_min, i_min = d[-1]
if d_min == d_child[i_min]:
    for a in ans:
        print(*a)
else:
     print(-1)
### BUGGY CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
agc 029 B
"""

from collections import Counter

n = int(input())
ali = list(map(int, input().split()))
ali.sort(reverse=True)

c = Counter(ali)
ans = 0


def pow2(n):
    m = n
    tmp = 1
    while m > 0:
        tmp = tmp << 1
        m = m >> 1
    return tmp


ii = 0
m = ali[ii]
while bool(c):
    n = pow2(m) - m
    c[m] -= 1
    if c[m] == 0:
        c += Counter()
        ii += 1
        m = ali[ii]
    if n in c:
        c[n] -= 1
        ans += 1
    c += Counter()

print(ans)








### FIXED CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
agc 029 B
"""

from collections import Counter

nn = int(input())
ali = list(map(int, input().split()))
ali.sort(reverse=True)

c = Counter(ali)
ans = 0


def pow2(n):
    m = n
    tmp = 1
    while m > 0:
        tmp = tmp << 1
        m = m >> 1
    return tmp


ii = 0
m = ali[ii]
while bool(c):
    while c[ali[ii]] == 0:
        ii += 1
    m = ali[ii]
    n = pow2(m) - m
    c[m] -= 1
    if c[m] <= 0:
        del c[m]
    if n in c:
        c[n] -= 1
        if c[n] <= 0:
            del c[n]
        ans += 1

print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()

new_S = S.replace("AC", "12")
# print(new_S)

for i in range(Q):
    left, right = map(int, input().split())
    # print(new_S[left-1:right-1], new_S[left-2:right])
    count_one = new_S[left-1:right-1].count('1')
    # count_two = new_S[left-1:right].count('2')
    print(count_one)

### FIXED CODE ###

import collections

N, Q = map(int, input().split())
S = input()

new_S = S.replace("AC", "12")


count_one_list = [0] * len(S)
for i in range(len(S)-1):
    if new_S[i] == '1' and i == 0:
        count_one_list[i+1] += 1
    elif new_S[i] == '1':
        count_one_list[i+1] = count_one_list[i] + 1
    else:
        count_one_list[i+1] = count_one_list[i]
# count_one_list = [new_S[:i].count('1') for i in range(len(S))]
# print(count_one_list)

for i in range(Q):
    left, right = map(int, input().split())
    count_one = count_one_list[right-1] - count_one_list[left-1]
    print(count_one)
### BUGGY CODE ###

def main():
    h, w = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(h)]
    b = [list(map(int, input().split())) for _ in range(h)]
    t = [[set() for j in range(w)] for i in range(h)]
    t[0][0].add(a[0][0] - b[0][0])
    for i in range(h):
        for j in range(w):
            if 0 < i and 0 < j:
                buf = t[i-1][j] | t[i][j-1]
                for v in buf:
                    t[i][j].add(v + (a[i][j] - b[i][j]))
                    t[i][j].add(v - (a[i][j] - b[i][j]))
            elif 0 < i:
                buf = t[i-1][j]
                for v in buf:
                    t[i][j].add(v + (a[i][j] - b[i][j]))
                    t[i][j].add(v - (a[i][j] - b[i][j]))
            elif 0 < j:
                buf = t[i][j-1]
                for v in buf:
                    t[i][j].add(v + (a[i][j] - b[i][j]))
                    t[i][j].add(v - (a[i][j] - b[i][j]))
    ans = float("inf")
    for v in t[i][j]:
        ans = min(ans, abs(v))
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np
def main():
    h, w = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(h)]
    b = [list(map(int, input().split())) for _ in range(h)]
    n = 80*(80+80) + 10
    m = n//2
    dp = [[None]*w for i in range(h)]
    for i in range(h):
        for j in range(w):
            dp[i][j] = np.zeros(n, np.bool)
    dp[0][0][m+abs(a[0][0] - b[0][0])] = True
    dp[0][0][m-abs(a[0][0] - b[0][0])] = True
    for i in range(h):
        for j in range(w):
            x = abs(a[i][j] - b[i][j])
            if 0 < i and 0 < h:
                dp[i][j][x:] |= dp[i-1][j][:n-x]
                dp[i][j][:n-x] |= dp[i-1][j][x:]
                dp[i][j][x:] |= dp[i][j-1][:n-x]
                dp[i][j][:n-x] |= dp[i][j-1][x:]
            elif 0 < i:
                dp[i][j][x:] |= dp[i-1][j][:n-x]
                dp[i][j][:n-x] |= dp[i-1][j][x:]
            elif 0 < j:
                dp[i][j][x:] |= dp[i][j-1][:n-x]
                dp[i][j][:n-x] |= dp[i][j-1][x:]
    ans = float("inf")
    for i in range(m-80-1, m+80+2):
        if dp[h-1][w-1][i]:
            ans = min(ans, abs(m-i))
    print(ans)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

from collections import Counter
MOD=2019
S=input();N=len(S)
Cum=[0]*(N+1)
for i in range(N):
    Cum[i+1]=(Cum[i]+int(S[N-i-1])*(10**i))%MOD
res=0
c=Counter(Cum).most_common()
for a,b in c:
    res+=b*(b-1)//2
    if(b==1):
        break
print(res)

### FIXED CODE ###

from collections import Counter
MOD=2019
S=input();N=len(S)
Cum=[0]*(N+1)
for i in range(N):
    Cum[i+1]=(Cum[i]+int(S[N-i-1])*pow(10,i,MOD))%MOD
res=0
c=Counter(Cum).most_common()
for a,b in c:
    res+=b*(b-1)//2
    if(b==1):
        break
print(res)
### BUGGY CODE ###

import math

def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    
    if K > 41:
        K = 41
    
    for k in range(K):
        B = [0 for i in range(N)]
        for i in range(N):
            low = max(0,i-A[i])
            high = min(N-1,i+A[i])
            B[low] += 1
            if high+1 < N:
                B[high+1] -= 1
        for i in range(1,N):
            B[i] += B[i-1]
        A = B
    
    print(*A)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    
    if K > 41:
        K = 41
    
    for k in range(K):
        B = [0 for i in range(N)]
        for i in range(N):
            low = max(0,i-A[i])
            high = min(N-1,i+A[i])
            B[low] += 1
            if high+1 < N:
                B[high+1] -= 1
        for i in range(1,N):
            B[i] += B[i-1]
        A = B
    
    print(*A)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
s = input()

def get_rest(si, sj):
    for c in ['R', 'G', 'B']:
        if not c in [si, sj]: return c

cnt = 0
for i in range(n):
    for j in range(i+1, n):
        if s[j] == s[i]: continue
        rest = get_rest(s[i], s[j])
        cnt += s[j+1:].count(rest)
        if j+(j-i) >= n: continue
        if s[j+(j-i)] == rest: cnt -= 1
print(cnt)

### FIXED CODE ###

n = int(input())
s = input()

colors = ['R', 'B', 'G']

cnt = 1
for c in colors:
    cnt *= s.count(c)

for i in range(n):
    w = 1
    while True:
        if i + 2*w >= n: break
        if s[i] != s[i+w] and s[i+w] != s[i+2*w] and s[i+2*w] != s[i]:
            cnt -= 1
        w += 1
print(cnt)
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    adj = [[] for _ in range(H*W)]
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    ans = 0
    
    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                tmp = 1
                for k in range(4):
                    y = i + dy[k]
                    x = j + dx[k]
                    while 0 <= y < H and 0 <= x < W:
                        if S[y][x] == '.':
                            tmp += 1
                            y += dy[k]
                            x += dx[k]
                        else:
                            break
                ans = max(ans, tmp)
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

#!/usr/bin/env python3

def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]

    # L[i][j]: このマスが光る時に左方向に照らされるマスの個数
    L = [[0]*W for _ in range(H)]
    R = [[0]*W for _ in range(H)]

    for i in range(H):
        for j in range(1,W):
            if S[i][j] == '.':
                if S[i][j-1] == '.': 
                    L[i][j] = L[i][j-1] + 1
            if S[i][W-j-1] == '.':
                if S[i][W-j] == '.': 
                    R[i][W-j-1] = R[i][W-j] + 1
    
    # U[i][j]: このマスが光る時に上方向に照らされるマスの個数
    U = [[0]*W for _ in range(H)]
    D = [[0]*W for _ in range(H)]

    for j in range(W):
        for i in range(1,H):
            if S[i][j] == '.':
                if S[i-1][j] == '.': 
                    U[i][j] = U[i-1][j] + 1
            if S[H-i-1][j] == '.':
                if S[H-i][j] == '.': 
                    D[H-i-1][j] = D[H-i][j] + 1
    ans = 0
    
    for i in range(H):
        for j in range(W):
            tmp = 1
            tmp += L[i][j] + R[i][j] + U[i][j] + D[i][j]
            ans = max(tmp,ans)
    
    print(ans)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N = int(input())
S = input()

S_dict = {}
for i, s in enumerate(list(S)):
    if s in S_dict:
        S_dict[s].append(i)
    else:
        S_dict[s] = [i]
#print(S_dict)

S_set = set()
for nums in S_dict.values():
    for i, a in enumerate(nums):
        for b in nums[i+1:]:
            S_set.add((a, b))
#print(S_set)
#print("---")

from copy import copy 
for i in range(0, N//2+1):
    tmp_set = copy(S_set)
    for a, b in tmp_set:
        if b+i < N and a+i < b and S[a+i] == S[b+i]:
            pass
        else:
            S_set.remove((a,b))
    #print(S_set)
    if len(S_set) == 0:
        print(i)
        break
    
    


### FIXED CODE ###

def resolve():
    import sys
    input=sys.stdin.readline
    N = int(input().rstrip())
    S = input().rstrip()

    def z_algo(s):
        """
        param s:str
        return list of int with length len(s)
        """
        # initialization
        n=len(s)
        z=[0]*n
        z[0]=n
        # construct
        L,R=0,0
        for i in range(1,n):
            if i>R: # 過去の結果が全く使えない
                L=R=i
                while(R<n and s[R-L]==s[R]): R+=1
                z[i]=R-L
                R-=1 # 0-indexedでiと比較するため
            elif z[i-L]<R-i+1:
                z[i]=z[i-L]
            else:
                L=i
                R+=1 # Rまでは確定しているので、R+1から確認
                while(R<n and s[R-L]==s[R]): R+=1
                z[i]=R-L
                R-=1
        return z

    ans = 0
    for i in range(N-1):
        z = z_algo(S[i:])
        for j, _z in enumerate(z):
            ans=max(ans,min(j,z[j]))
    print(ans)

resolve()
### BUGGY CODE ###

n = int(input())
s_list = []
ana = 0
for i in range(n):
    s = sorted(input())
    if len(s_list) > 0:
        for s_i in s_list:
            if s_i == s:
                ana += 1
    s_list.append(s)
print(ana)

### FIXED CODE ###

n = int(input())
s_dict = {}
ana = 0
for i in range(n):
    s = "".join(sorted(input()))
    #print(s)
    if s in s_dict:
        ana += s_dict[s]
        s_dict[s] += 1
    else:
        s_dict[s] = 1
        
print(ana)
### BUGGY CODE ###

from operator import mul
from functools import reduce
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
ansma=0
ansmi=0
for i in range(n):
  if n-i-1>=k-1:
    ansma+=cmb(n-i-1,k-1)*a[n-i-1]
a.sort(reverse=True)
for i in range(n):
  if n-i-1>=k-1:
    ansmi+=cmb(n-i-1,k-1)*a[n-i-1]
print((ansma-ansmi)%(10**9+7))

### FIXED CODE ###

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
ansma=0
ansmi=0
for i in range(n):
  if n-i-1>=k-1:
    ansma+=cmb(n-i-1,k-1,mod)*a[n-i-1]
    ansmi+=cmb(n-i-1,k-1,mod)*a[i]
print((ansma-ansmi)%mod)
### BUGGY CODE ###

from collections import deque
N, K = map(int, input().split())
combs = deque()
ans = 0
a = 1
while a <= N:
  b = K - a
  while b <= N:
    if b >=  a:
      c = K - a
      while c <= N:
        if c >= b and (b+c)%K == 0 and (c+a)%K == 0:
          combs.append([a, b, c])
        c += K
    b += K
  a += 1
for (a, b, c) in combs:
  if a==b and b==c:
    ans += 1
  elif a == b or b == c or c == a:
    ans += 3
  else:
    ans += 6
print(ans)

### FIXED CODE ###

from collections import deque
N, K = map(int, input().split())
ans = (N // K)**3
if K % 2 == 0:
  m = K // 2
  cnt = 0
  i = m
  while i <= N:
    i += K
    cnt += 1
  ans += cnt**3
print(ans)
### BUGGY CODE ###

n = int(input())

a = []
for i in range(n):
    a.append(int(input()))

if a[0] > 0:
    print(-1)
    exit()

for i in range(1, n):
    if a[i] > i:
        print(-1)
        exit()
    if a[i] > a[i-1] + 1:
        print(-1)
        exit()

result = 0
b = [0 for i in range(n)]
while a != b:
    max_diff = 0
    for i in range(n):
        if a[i] != b[i]:
            if a[i] > max_diff:
                start = i
                max_diff = a[i]
    for i in range(max_diff):
        if b[start - i] != a[start - i]:
            b[start - i] = max_diff - i
    result += max_diff

print(result)


### FIXED CODE ###

n = int(input())

a = []
for i in range(n):
    a.append(int(input()))

if a[0] > 0:
    print(-1)
    exit()

for i in range(1, n):
    if a[i] > i:
        print(-1)
        exit()
    if a[i] > a[i - 1] + 1:
        print(-1)
        exit()

if n == 1:
    print(0)
    exit()

result = 0

if a[n-1] != 0:
    result += a[n-1]

for i in range(2, n):
    j = n - i
    if a[j] != 0 and a[j] != a[j + 1] - 1:
            result += a[j]

print(result)
### BUGGY CODE ###

def culc_expected_value(num):
  output = 0
  if num != 1:
    for i in range(1, num+1):
      output = output + i/num
  else:
    output = 1
  return output
 
n, k = map(int, input().split())
p_list = list(map(int, input().split()))
max_nums = 0
max_targets = []
for j in range(0, len(p_list)-k+1):
  targets = [p_list[j+m] for m in range(k)]
  t_sum = sum(targets)
  if t_sum >= max_nums:
    max_nums = t_sum
    max_targets = targets
# print(max_targets)

ans = 0
for t in max_targets:
  ans += culc_expected_value(t)
  # print(ans)

print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
p_list = list(map(int, input().split()))
tmp = sum(p_list[:k])
max_num = sum(p_list[:k])
for i in range(len(p_list)-k):
  tmp = tmp - p_list[i] + p_list[i+k]
  if tmp >= max_num:
    max_num = tmp
print((max_num+k)/2)
### BUGGY CODE ###

n, k = [int(i) for i in input().split()]
cnt = 0
for i in range(1,2*n//k+1):
    if i*k%2 ==1 and k%2 == 1:
        for j in range((i-1)//2):
            a = i*k//2 - (k+2*k*j-1)//2
            if i * k - a <= n:
                cnt += ((a+n)//k - a//k)*2
    elif i*k%2 == 0:
        if k%2 == 0:
            for j in range(i-1):
                a = i * k // 2 - (k + k * j) // 2
                if i*k-a <= n:
                    cnt += ((a + n) // k - a // k) * 2
        else:
            for j in range(1,i // 2):
                a = i * k // 2 - k * j
                if i * k - a <= n:
                    cnt += ((a + n) // k - a // k) * 2
        cnt += ((i*k//2 + n) // k - (i*k//2) // k)
print(cnt)


### FIXED CODE ###

N, K = [int(i) for i in input().split()]
cnt = 0
if K % 2 == 0:
    for i in range(1, 2*N//K+1):
        cnt += 1 + (2*N//K-i)//2 * 6 + (2*N//K-i)//2 * ((2*N//K-i)//2 - 1) * 3
else:
    for i in range(1, N//K+1):
        cnt += 1 + (N//K-i) * 6 + (N//K-i) * ((N//K-i) - 1) * 3

print(cnt)
### BUGGY CODE ###

H=int(input())
i=0
count=1
while True:
    H=H//2
    i+=1
    count+=2**i
    if H==1:
        print(count)
        break

### FIXED CODE ###

H = int(input())
if H==1:
    print(1)
else:
    for i in range(1, 50):
        if 2**i <= H < 2**(i+1):
            print(2**(i+1)-1)
### BUGGY CODE ###

from collections import Counter
import sys
input = sys.stdin.readline

def Washall_Floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d
  
def flatten_2dim(array):
    return [item for sublist in array for item in sublist]

n, x, y = map(int, input().split())
f_inf = float('inf')
dist = [[f_inf] * n for _ in range(n)]
for i in range(n): dist[i][i] = 0

for i in range(n-1):
    dist[i][i+1] = 1
    dist[i+1][i] = 1

dist[x-1][y-1]=1
dist[y-1][x-1]=1
Washall_Floyd(dist)

counter = Counter(flatten_2dim(dist))
counter = sorted(counter.most_common())[1:]

for key, val in counter:
    print(val//2)
for _ in range(n - len(counter)-1):
    print(0)

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

f_inf = float('inf')

def push(v, d):
    if dist[v] != f_inf: return
    dist[v] = d
    que.append(v)

n, x, y = map(int, input().split())
x -= 1
y -= 1

ans = [0]*n
for sv in range(n):
    dist = [f_inf] * n
    que = deque([])
    push(sv, 0)

    while que:
        v = que.popleft()
        d = dist[v]+1
        if v-1 >= 0: push(v-1, d)
        if v+1 < n: push(v+1, d)
        if v == x: push(y, d)
        if v == y: push(x, d)

    for i in range(n):
        ans[dist[i]] += 1
        
for i in range(n):
    ans[i] = ans[i]//2

for i in range(1, n):
    print(ans[i])
### BUGGY CODE ###

def div(n):
    a = []
    for i in range(2,n+1):
        while n % i == 0:
            a.append(i)
            n //= i
    return a

a,b = map(int,input().split())
c = list(set(div(a)) & set(div(b)))
ans = len(c)
print(ans+1)

### FIXED CODE ###

import math
def div(n):
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
def is_primeplus(n):
    if n == 1:
        return 1
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return 0
    return 1
a,b = map(int,input().split())
c = list(set(div(a)) & set(div(b)))
ans = 0
for i in range(len(c)):
    if is_primeplus(c[i]):
        ans += 1
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
contain_one = [j for i, j in ab if i == 1]
string_ab = [str(k)+str(l) for k, l in ab]

for b in contain_one:
    if str(b)+str(n) in set(string_ab):
        print("POSSIBLE")
        exit()
else:
    print("IMPOSSIBLE")


### FIXED CODE ###

n, m = map(int, input().split())
ab = []
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        ab.append(b)
    if b == n:
        ab.append(a)

if len(ab) != len(set(ab)):
        print("POSSIBLE")
        exit()
else:
    print("IMPOSSIBLE")