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

def solve(n, g):
    mod = 10 ** 9 + 7

    dp_w = [1] * n
    dp_b = [1] * n

    # dp_x[j] := 頂点jをxとする場合のjを親とする部分木の塗り方の状態数
    # dp_w[j] = reduce(mul, (dp_w[k] + dp_b[k] for k in g[j]))
    # dp_b[j] = reduce(mul, (dp_w[k] for k in g[j]))

    def dfs(v):
        checked[v] = True
        for u in g[v]:
            if checked[u]:
                continue
            dfs(u)
            dp_w[v] = dp_w[v] * (dp_w[u] + dp_b[u]) % mod
            dp_b[v] = dp_b[v] * dp_w[u] % mod

    checked = [False] * n
    checked[0] = True
    dfs(0)

    return (dp_w[0] + dp_b[0]) % mod


if __name__ == '__main__':
    import sys

    sys.setrecursionlimit(10 ** 7)

    input = sys.stdin.readline

    n = int(input())
    g = tuple(set() for _ in range(n))
    for _ in range(n - 1):
        x, y = (int(j) - 1 for j in input().rstrip().split())
        g[x].add(y)
        g[y].add(x)
    print(solve(n, g))

# 適当な頂点を根とする


### FIXED CODE ###

def solve(n, g):
    mod = 10 ** 9 + 7

    def dfs(v):
        checked[v] = True

        w = 1
        b = 1
        for u in g[v]:
            if checked[u]:
                continue
            uw, ub = dfs(u)
            w = w * (uw + ub) % mod
            b = b * uw % mod
        return w, b

    stack = [0]
    order = []
    parent = [-1] * n
    checked = [False] * n
    checked[0] = True

    while stack:
        v = stack.pop()
        order.append(v)
        for u in g[v]:
            if checked[u]:
                continue
            checked[u] = True
            parent[u] = v
            stack.append(u)

    order.reverse()

    checked = [False] * n

    dp_w = [1] * n
    dp_b = [1] * n

    for v in order:
        checked[v] = True
        par = parent[v]
        if par == -1:
            continue
        dp_w[par] = (dp_w[par] * (dp_w[v] + dp_b[v])) % mod
        dp_b[par] = (dp_b[par] * dp_w[v]) % mod

    v = order[-1]
    return (dp_w[v] + dp_b[v]) % mod


if __name__ == '__main__':
    import sys

    input = sys.stdin.readline

    n = int(input())
    g = tuple(set() for _ in range(n))
    for _ in range(n - 1):
        x, y = (int(j) - 1 for j in input().rstrip().split())
        g[x].add(y)
        g[y].add(x)
    print(solve(n, g))

# 適当な頂点を根とする
# 2次元配列でdpするより、1次元*2本の方が若干速い
### BUGGY CODE ###

def password():
    for i in range(10):
        for j in range(10):
            for k in range(10):
                yield [str(i), str(j), str(k)]


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

ans = 0
for perm in password():
    j = 0
    for i in range(len(s)):
        if perm[j] == s[i]:
            j += 1
            if j >= len(perm):
                break
    if j >= len(perm):
        ans += 1

print(ans)

### FIXED CODE ###

def password():
    for i in range(10):
        for j in range(10):
            for k in range(10):
                yield [str(i), str(j), str(k)]


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

ans = 0
for perm in password():
    if perm[0] in s:
        a = s.find(perm[0])
        if perm[1] in s[a + 1 :]:
            b = s[a + 1 :].find(perm[1])
            if perm[2] in s[a + 1 :][b + 1 :]:
                ans += 1

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

import sys
from collections import deque


H,W=map(int, raw_input().split())
A=[ list( sys.stdin.readline().strip())  for i in range(H) ]


D=[ (-1,0),(1,0),(0,1),(0,-1) ]
K=[ [ float("inf") for j in range(W) ] for i in range(H)  ]  #Kyori

def bfs(h,w):
	q=deque()
	K[h][w]=0
	q.append( (h,w) )
	while q:
		h, w=q.popleft()	# newh , neww
		for dx,dy in D:
			if 0<=h+dx<H and 0<=w+dy<W:
				if A[h+dx][w+dy]=="." and K[h+dx][w+dy]>K[h][w]:
					K[h+dx][w+dy]=min( K[h+dx][w+dy], K[h][w]+1 )
					q.append( (h+dx,w+dy) )	


for i in range(H):
	for j in range(W):
		if A[i][j]=="#":
			bfs(i,j)

ans=0
for i in range(H):
	ans=max(ans , max(K[i]))

print ans

### FIXED CODE ###

import sys
from collections import deque

H,W=map(int, raw_input().split())
A=[ list( sys.stdin.readline().strip())  for i in range(H) ]


D=[ (-1,0),(1,0),(0,1),(0,-1) ]
K=[ [ float("inf") for j in range(W) ] for i in range(H)  ]  #Kyori

q=deque()

for i in range(H):
	for j in range(W):
		if A[i][j]=="#":
			q.append( (i,j) )
			K[i][j]=0


while q:
	h,w=q.popleft()
	for dx,dy in D:
		if 0<=h+dx<H and 0<=w+dy<W and K[h+dx][w+dy]>K[h][w]+1:
				K[h+dx][w+dy]=K[h][w]+1
				q.append( (h+dx,w+dy) )	

ans=0
for x in K:
	ans=max(ans, max(x) )
print ans
### BUGGY CODE ###

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

blist = []
for i in range(n) :
    bi = alist.pop(0)
    if (n^i)&1 == 1 :
        blist.insert(0, bi)
    else :
        blist.append(bi)

for b in blist :
    print(b, end=" ")

### FIXED CODE ###

from collections import deque
n = int(input())
alist = deque(map(int, input().split()))

blist = deque([])
for i in range(n) :
    bi = alist.popleft()
    if (n^i)&1 == 1 :
        blist.appendleft(bi)
    else :
        blist.append(bi)

for b in blist :
    print(b, end=" ")
### BUGGY CODE ###

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

cnt = [0] * 1000
for i in range(len(s)-2):
    for j in range(i+1, len(s)-1):
        for k in range(j+1, len(s)):
            S = ''.join([s[i], s[j], s[k]])
            cnt[int(S)] += 1

ans = 0
for i in range(len(cnt)):
    if cnt[i] > 0:
        ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = list(input())
PIN = []
b1 = []
for i in range(N-2):
    b2 = []
    if S[i] in b1:
        continue
    else:
        b1.append(S[i])
    for j in range(i+1, N-1):
        b3 = []
        if S[j] in b2:
            continue
        else:
            b2.append(S[j])
        for k in range(j+1, N):
            if S[k] in b3:
                continue
            else:
                b3.append(S[k])
            cand = S[i] + S[j] + S[k]
            PIN.append(cand)

print(len(set(PIN)))
### BUGGY CODE ###

import itertools

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

NOW=[0]*(K+1)
NOW[0]=1#そこまでi個使ったときの場合の数


for a in A:
    NEXT=[0]*(K+1)
    NOWSUM=list(itertools.accumulate(NOW))
    NEXT=[NOWSUM[i]  if i<=a else 0 for i in range(K+1)]
    #print(NEXT)

    for j in range(a+1,K+1):
        NEXT[j]=(NOWSUM[j]-NOWSUM[j-a-1])%mod


    NOW=NEXT
    #print(NOWSUM,NOW)

print(NOW[K]%mod)

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

NOW=[0]*(K+1)
NOW[0]=1#そこまでi個使ったときの場合の数


for i in range(N):
    NEXT=[0]*(K+1)
    NOWSUM=[0]
    for n in NOW:
        NOWSUM.append(NOWSUM[-1]+n)
        
    for j in range(K+1):
        NEXT[j]=(NEXT[j]+NOWSUM[j+1]-NOWSUM[max(0,j-A[i])])%mod

    NOW=NEXT
    #print(NOWSUM,NOW)

print(NOW[K])
### BUGGY CODE ###

H,W=list(map(int,input().split()))
l=[list(input()) for i in range(H)]
l_count=[[0]*W for i in range(H)]
from collections import deque
def answer(st_X,st_Y):#X,Y座標を指定してそこからの距離を考える
   tmp_X,tmp_Y=st_X,st_Y
   que=deque([[tmp_X,tmp_Y,0]])
   after=deque([])
   while que:#スタート地点からの距離を数えながら行ったことのない場所を探索する
      tmp_X,tmp_Y,nu=que.popleft()
      after.append([tmp_X,tmp_Y])
      if tmp_X>0 and l[tmp_Y][tmp_X-1]=="." and [tmp_X-1,tmp_Y] not in after and [tmp_X-1,tmp_Y] not in que:
         l_count[tmp_Y][tmp_X-1]=nu+1
         que.append([tmp_X-1,tmp_Y,nu+1])
      if tmp_Y>0 and l[tmp_Y-1][tmp_X]=="." and [tmp_X,tmp_Y-1] not in after and [tmp_X-1,tmp_Y] not in que:
         l_count[tmp_Y-1][tmp_X]=nu+1
         que.append([tmp_X,tmp_Y-1,nu+1])
      if tmp_X<W-1 and l[tmp_Y][tmp_X+1]=="." and [tmp_X+1,tmp_Y] not in after and [tmp_X-1,tmp_Y] not in que:
         l_count[tmp_Y][tmp_X+1]=nu+1
         que.append([tmp_X+1,tmp_Y,nu+1])
      if tmp_Y<H-1 and l[tmp_Y+1][tmp_X]=="." and [tmp_X,tmp_Y+1] not in after and [tmp_X-1,tmp_Y] not in que:
         l_count[tmp_Y+1][tmp_X]=nu+1
         que.append([tmp_X,tmp_Y+1,nu+1])
ans=0
for i in range(H):
   for j in range(W):
      if l[i][j]==".":
         l_count=[[0]*W for i in range(H)]
         answer(j,i)
         tmp=max(sum(l_count,[]))
         ans=max(ans,tmp)
print(ans)

### FIXED CODE ###

H,W=list(map(int,input().split()))
l=[list(input()) for i in range(H)]
l_count=[[0]*W for i in range(H)]
from collections import deque
def answer(st_X,st_Y):#X,Y座標を指定してそこからの距離を考える
   tmp_X,tmp_Y=st_X,st_Y
   que=deque([[tmp_X,tmp_Y]])
   after=set()
   while que:#スタート地点からの距離を数えながら行ったことのない場所を探索する
      tmp_X,tmp_Y=que.popleft()
      nu=l_count[tmp_Y][tmp_X]
      after.add((tmp_X,tmp_Y))
      if tmp_X>0 and l[tmp_Y][tmp_X-1]=="." and (tmp_X-1,tmp_Y) not in after and [tmp_X-1,tmp_Y] not in que:
         l_count[tmp_Y][tmp_X-1]=nu+1
         que.append([tmp_X-1,tmp_Y])
      if tmp_Y>0 and l[tmp_Y-1][tmp_X]=="." and (tmp_X,tmp_Y-1) not in after and [tmp_X,tmp_Y-1] not in que:
         l_count[tmp_Y-1][tmp_X]=nu+1
         que.append([tmp_X,tmp_Y-1])
      if tmp_X<W-1 and l[tmp_Y][tmp_X+1]=="." and (tmp_X+1,tmp_Y) not in after and [tmp_X+1,tmp_Y] not in que:
         l_count[tmp_Y][tmp_X+1]=nu+1
         que.append([tmp_X+1,tmp_Y])
      if tmp_Y<H-1 and l[tmp_Y+1][tmp_X]=="." and (tmp_X,tmp_Y+1) not in after and [tmp_X,tmp_Y+1] not in que:
         l_count[tmp_Y+1][tmp_X]=nu+1
         que.append([tmp_X,tmp_Y+1])
ans=0
for i in range(H):
   for j in range(W):
      if l[i][j]==".":
         l_count=[[0]*W for i in range(H)]
         answer(j,i)
         tmp=max(sum(l_count,[]))
         ans=max(ans,tmp)
print(ans)
### BUGGY CODE ###

# coding: utf-8
import sys
import numpy as np

N, W = map(int, sys.stdin.buffer.readline().split())
   
dp = np.ones(W+1, dtype=int) * -1
dp[0] = 0

for i in range(1, N+1):
    w, v = map(int, sys.stdin.buffer.readline().split())
    for j in range(W-w, -1, -1):
        if dp[j] == -1:
            continue
        if dp[j+w] < dp[j]+v:
            dp[j+w] = dp[j] + v

# for i in range(N+1):
#     print(dp[i])

print(max(dp))

### FIXED CODE ###

def main():
    N, W = map(int, input().split())
 
    dp = [-1] * (W + 1)
    dp[0] = 0
    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(W - w, -1, -1):
            if dp[i] == -1:
                continue
            if dp[i + w] < dp[i] + v:
                dp[i + w] = dp[i] + v
    print(max(dp))
 
 
main()
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]

l = []
A2 = sorted(A)
for i in range(N):
    a = A2[i]
    idx = A.index(a)
    l.append(idx + 1)
print(*l)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]

l = [0] * N

for i, a in enumerate(A):
    l[int(a - 1)] = str(i + 1)
print(*l)
### BUGGY CODE ###

from heapq import heapify

N, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for i in range(N)]
heapify(wv)
wv = [None] + wv

dp = [{0: 0}] + [{} for i in range(N)]

for i in range(1, N+1):
  w, v = wv[i]
  for mw, mv in dp[i-1].items():
    dp[i][mw] = max(dp[i].get(mw, 0), dp[i-1].get(mw, 0))
    if mw + w < W+1:
      dp[i][mw+w] = max(dp[i].get(mw+w, 0), dp[i-1][mw]+v, dp[i-1].get(mw+w, 0))

print(max(dp[N].values()))

### FIXED CODE ###

import sys
input = sys.stdin.readline

def dp_fn():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))
  
  DP = {0:0}
  
  for w, v in WV:
    keys = sorted(DP.keys(), reverse=True)
    for i in keys:
      j = DP[i]
      if j+w <= W:
        if i+v in DP:
          DP[i+v] = min(DP[i+v], j+w)
        else:
          DP[i+v] = j+w
  return max(DP.keys())
  
print(dp_fn())
### BUGGY CODE ###

from collections import Counter
from math import factorial
N=int(input())
A=list(map(int,input().split()))
for i in range(N):
    B=Counter(A[:i]+A[i+1:])
    count=0
    for b in B.values():
        if b >= 2:
            count+=factorial(b)//(factorial(b-2)*factorial(2))
    print(count)


### FIXED CODE ###

from collections import Counter
from math import factorial
N=int(input())
A=list(map(int,input().split()))
B=Counter(A)
count=0
def combination(x,y):
    return factorial(x) // (factorial(x - y) * factorial(y))
for key,b in B.items():
    if b>=2:
        count+=combination(b,2)
for a in A:
    ans=count
    ans-=B[a]-1
    print(ans)
### BUGGY CODE ###

A,B,Q=map(int,input().split())
S=[-int(1e10)]+[int(input()) for _ in range(A)]+[int(2e10)]
T=[-int(1e10)]+[int(input()) for _ in range(B)]+[int(2e10)]
for _ in range(Q):
    x=int(input())
    seq=False
    teq=False
    su=A+1
    sl=0
    while su-sl>1:
        t=(su+sl)//2
        if S[t]==x:
            seq=True
            break
        if S[t]>x: su=t
        else: sl=t
    tu=B+1
    tl=0
    while tu-tl>1:
        t=(tu+tl)//2
        if T[t]==x:
            teq=True
            break
        if T[t]>x: tu=t
        else: tl=t
    
    if seq and teq:
        print(0)
    elif seq:
        print(min(x-T[tl],T[tu]-x))
    elif teq:
        print(min(x-S[sl],S[su]-x))
    else:
        SU=S[su]-x
        TU=T[tu]-x
        SL=x-S[sl]
        TL=x-T[tl]
        print(min([max(SU,TU), max(SL,TL), SU*2+TL, TL*2+SU, TU*2+SL, SL*2+TU]))

### FIXED CODE ###

A,B,Q=map(int,input().split())
S=[-int(1e10)]+[int(input()) for _ in range(A)]+[int(2e10)]
T=[-int(1e10)]+[int(input()) for _ in range(B)]+[int(2e10)]
for _ in range(Q):
    x=int(input())
    seq=False
    teq=False
    su=A+1
    sl=0
    while su-sl>1:
        t=(su+sl)//2
        if S[t]==x:
            seq=True
            break
        if S[t]>x: su=t
        else: sl=t
    tu=B+1
    tl=0
    while tu-tl>1:
        t=(tu+tl)//2
        if T[t]==x:
            teq=True
            break
        if T[t]>x: tu=t
        else: tl=t
    
    if seq and teq:
        print(0)
    elif seq:
        print(min(x-T[tl],T[tu]-x))
    elif teq:
        print(min(x-S[sl],S[su]-x))
    else:
        SU=S[su]-x
        TU=T[tu]-x
        SL=x-S[sl]
        TL=x-T[tl]
        print(min([max(SU,TU), max(SL,TL), SU*2+TL, TL*2+SU, TU*2+SL, SL*2+TU]))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))

B = []

if N % 2 == 0:
  for index, a in enumerate(A):
    if index % 2 == 1:
      B.insert(0, a)
    else:
      B.append(a)
else:
  for index, a in enumerate(A):
    if index % 2 == 0:
      B.insert(0, a)
    else:
      B.append(a)

for b in B:
  print(b, end=" ")

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))

B = []
T = []

if N % 2 == 0:
  for index, a in enumerate(A):
    if index % 2 == 1:
      T.append(a)
    else:
      B.append(a)
else:
  for index, a in enumerate(A):
    if index % 2 == 0:
      T.append(a)
    else:
      B.append(a)

T.reverse()
T.extend(B)


for b in T:
  print(b, end=" ")
### BUGGY CODE ###

N=int(input())
S=list(map(int,input().split()))
count=0
P=[0]*(N*N+1)
for j in range(N*N):
  P[j+1]=S.index(j+1)
for i in range(N*N):
  player=S[i]
  hayasa=P[player]
  
  que=[[] for _ in range(N)]
  d=[-1]*(N*N+1)
  que[0].append(player)
  d[player]=0
  
  j=0
  finish=0
  while True:
    for kouho in que[j]:
      if kouho%N==0:
        finish=1
        break
      if kouho%N==1:
        finish=1
        break
      if kouho+N>N*N:
        finish=1
        break
      if kouho<N:
        finish=1
        break
        
      if d[kouho+N]==-1:
        if P[kouho+N]>hayasa:
          que[j+1].append(kouho+N)
          d[kouho+N]=0
        else:
          que[j].append(kouho+N)
          d[kouho+N]=0
          
      if d[kouho-N]==-1:
        if P[kouho-N]>hayasa:
          que[j+1].append(kouho-N)
          d[kouho-N]=0
        else:
          que[j].append(kouho-N)
          d[kouho-N]=0
          
      if d[kouho+1]==-1:
        if P[kouho+1]>hayasa:
          que[j+1].append(kouho+1)
          d[kouho+1]=0
        else:
          que[j].append(kouho+1)
          d[kouho+1]=0
          
      if d[kouho-1]==-1:
        if P[kouho-1]>hayasa:
          que[j+1].append(kouho-1)
          d[kouho-1]=0
        else:
          que[j].append(kouho-1)
          d[kouho-1]=0
    if finish==1:
      count+=j
      break
    j+=1    
print(count)

### FIXED CODE ###

from numba import njit
import numpy as np

@njit
def main(N, P):
    lista = [1, -1, N, -N]
    d = np.zeros((N, N), dtype=np.int32)
    d = d.ravel()
    sit = np.ones_like(d)
    stack = np.empty_like(d)
    count = 0
    for i in range(N*N):
        d[i] = min(i % N, (N-1-i) % N, i//N, N-1-i//N)
    for player in P:
        sit[player-1] = 0
        count += d[player-1]
        stack[0] = player
        num = 0
        while num >= 0:
            p = stack[num]
            num -= 1
            a = d[p-1]+sit[p-1]
            for i in lista:
                if p+i < 1 or p + i > N*N:
                    continue
                if d[p+i-1] > a:
                    d[p+i-1] = a
                    num += 1
                    stack[num] = p+i
    print(count)

N = int(input())
P = np.array(input().split(), np.int32)

main(N, P)
### BUGGY CODE ###

n,ma,mb,*L=map(int,open(0).read().split())
INF=float('inf')
dp=[[INF]*420 for _ in range(420)]
dp[0][0]=0
for a,b,c in zip(*[iter(L)]*3):
	for i in range(400,-1,-1):
		for j in range(400,-1,-1):
			t=dp[i][j]+c
			if dp[i+a][j+b]>t:
				dp[i+a][j+b]=t
ans=INF
_ma,_mb=ma,mb
while _ma<410>_mb:
	ans=min(ans,dp[_ma][_mb])
	_ma+=ma
	_mb+=mb
print(ans if ans<INF else -1)

### FIXED CODE ###

n,ma,mb,*L=map(int,open(0).read().split())
INF=float('inf')
dp=[[INF]*420 for _ in range(420)]
dp[0][0]=0
for a,b,c in zip(*[iter(L)]*3):
	for i in range(400,-1,-1):
		for j in range(400,-1,-1):
			t=dp[i][j]+c
			if dp[i+a][j+b]>t:
				dp[i+a][j+b]=t
ans=INF
_ma,_mb=ma,mb
while _ma<410>_mb:
	ans=min(ans,dp[_ma][_mb])
	_ma+=ma
	_mb+=mb
print(ans if ans<INF else -1)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10**7)

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m = na()
h = na()
g = [[] for i in range(n)]
for i in range(m):
    a, b = na()
    g[a-1].append(b-1)
    g[b-1].append(a-1)

def dfs(v):
    seen[v] = True 
    for i in range(len(g[v])):
        nv = g[v][i]
        if seen[nv] == False:
            if h[v] > h[nv]:
                dfs(nv)
            else:
                return 0
    return 1
ans = 0  

for i in range(n):
    seen = [False] * n
    ans += dfs(i)
print(ans)

### FIXED CODE ###

import sys

sys.setrecursionlimit(10**7)

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m = na()
h = na()
mh = [0 for i in range(n)]
for i in range(m):
    a, b = na()
    mh[a-1] = max(mh[a-1], h[b-1])
    mh[b-1] = max(mh[b-1], h[a-1])
ans = 0  
for i in range(n):
    if h[i] > mh[i]:
        ans += 1
print(ans)
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from heapq import heappop, heappush, heapify

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def dijkstra(E, start):
    N_d = len(E)
    dist = [INF] * N_d
    dist[start] = 0
    q = [(0, start)]
    while q:
        dist_v, v = heappop(q)
        if dist[v] != dist_v:
            continue
        for u, dist_vu in E[v]:
            dist_u = dist_v + dist_vu
            if dist_u < dist[u]:
                dist[u] = dist_u
                heappush(q, (dist_u, u))
    return dist

N, X, Y = MAP()

graph = defaultdict(list)

for i in range(N-1):
    graph[i].append((i+1, 1))
    graph[i+1].append((i, 1))

graph[X-1].append((Y-1, 1))
graph[Y-1].append((X-1, 1))

a = dijkstra(graph, 0)
count = defaultdict(int)
for i in range(N):
    a = dijkstra(graph, i)
    
    # print(a[i+1:])
    for c in a[i+1:]:
        count[c] += 1
# print(count)

for i in range(1, N):
    print(count[i])

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from heapq import heappop, heappush, heapify
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
def dijkstra(E, start):
    N_d = len(E)
    dist = [INF] * N_d
    dist[start] = 0
    q = [(0, start)]
    while q:
        dist_v, v = heappop(q)
        if dist[v] != dist_v:
            continue
        for u, dist_vu in E[v]:
            dist_u = dist_v + dist_vu
            if dist_u < dist[u]:
                dist[u] = dist_u
                heappush(q, (dist_u, u))
    return dist
 
N, X, Y = MAP()
 
graph = defaultdict(list)
 
for i in range(N-1):
    graph[i].append((i+1, 1))
    graph[i+1].append((i, 1))
 
graph[X-1].append((Y-1, 1))
graph[Y-1].append((X-1, 1))
 
a = dijkstra(graph, 0)
count = defaultdict(int)
for i in range(N):
    a = dijkstra(graph, i)
    
    # print(a[i+1:])
    for c in a[i+1:]:
        count[c] += 1
# print(count)
 
for i in range(1, N):
    print(count[i])
### BUGGY CODE ###

def main():
    INF = 10 ** 6
    H, W = list(map(int, input().split(' ')))
    A = [input() for _ in range(H)]
    d = [[INF for _ in range(W)] for _ in range(H)]
    # 距離テーブルの初期化
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                d[h][w] = 0
    # 黒マスまでの横方向の最短距離を出す
    for h in range(H):
        # 左から右方向へ探索
        for w in range(1, W):
            d[h][w] = min(d[h][w], 1 + d[h][w - 1])
        # 逆方向
        for w in range(W - 2, -1, -1):
            d[h][w] = min(d[h][w], 1 + d[h][w + 1])
    # 縦方向も同様に探索
    for w in range(W):
        for h in range(1, H):
            d[h][w] = min(d[h][w], 1 + d[h - 1][w])
        for h in range(H - 2, -1, -1):
            d[h][w] = min(d[h][w], 1 + d[h + 1][w])
    # 黒マスまでの最長距離が答え
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, d[h][w])
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    INF = 10 ** 6
    H, W = list(map(int, input().split(' ')))
    A = [input() for _ in range(H)]
    d = [[INF for _ in range(W)] for _ in range(H)]
    # 距離テーブルの初期化
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                d[h][w] = 0
    # 黒マスまでの横方向の最短距離を出す
    for h in range(H):
        # 左から右方向へ探索
        for w in range(1, W):
            d[h][w] = min(d[h][w], 1 + d[h][w - 1])
        # 逆方向
        for w in range(W - 2, -1, -1):
            d[h][w] = min(d[h][w], 1 + d[h][w + 1])
    # 縦方向も同様に探索
    for w in range(W):
        for h in range(1, H):
            d[h][w] = min(d[h][w], 1 + d[h - 1][w])
        for h in range(H - 2, -1, -1):
            d[h][w] = min(d[h][w], 1 + d[h + 1][w])
    # 黒マスまでの最長距離が答え
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, d[h][w])
    print(ans)


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

# -*- coding: utf-8 -*-

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

apple_price = list(map(int, input().split()))
price_diff = []

for i in range(n):
    for j in range(i,n):
        diff = apple_price[j] - apple_price[i]
        if(diff>0):
            price_diff.append(diff)

print(price_diff.count(max(price_diff)))

### FIXED CODE ###

# -*- coding: utf-8 -*-

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

apple_price = list(map(int, input().split()))
price_diff = []
now_min = 10**9


for i in range(n):
    if(now_min > apple_price[i]):
        now_min = apple_price[i]
    else:
        price_diff.append(apple_price[i] - now_min)

if(price_diff):
    print(price_diff.count(max(price_diff)))
else:
    print(0)