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

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n, M = map(int, input().split())
ns = defaultdict(list)
for _ in range(n-1):
    u,v = map(int, input().split())
    ns[u-1].append(v-1)
    ns[v-1].append(u-1)

bs = {}
cump0 = defaultdict(list)
cump1 = defaultdict(list)
def sub(u, p):
    if (p,u) in bs:
        return bs[p,u]
    b = 1
    ps = []
    for v in ns[u]:
        if v==p:
            continue
        bb = sub(v, u)
        b *= (1+bb)
        b %= M
        ps.append(bb)
    v0 = 1
    v1 = 1
    l = len(ps)
    for i in range(l):
        cump0[u].append(v0)
        cump1[u].append(v1)
        v0 *= ps[i]+1
        v1 *= ps[l-1-i]+1
        v0%=M;v1%=M
    cump0[u].append(v0)
    cump1[u].append(v1)
        
    bs[p,u] = b % M
    return b

ans = [None]*n
def sub2(u, p):
    i = 0
    for v in ns[u]:
        if v==p:
            continue
        b1 = bs[p,u]
        b2 = bs[u,v]
        b3 = bs[u,p]
        if p>=0:
            bb = (cump0[u][i] * cump1[u][-(i+2)] * (1+b3)) % M
        else:
            bb = (cump0[u][i] * cump1[u][-(i+2)]) % M
        bs[v,u] = bb
        ans[v] = bs[u,v] * (1+bb) % M
        sub2(v,u)
        i += 1
        
sub(0, -1)
bs[0,-1] = 1
ans[0] = bs[-1,0]
sub2(0,-1)

# for u in range(n):
#     ans[u] = sub(u, -1)[1] % M
write("\n".join(map(str, ans)))

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n, M = map(int, input().split())
ns = defaultdict(list)
for _ in range(n-1):
    u,v = map(int, input().split())
    ns[u-1].append(v-1)
    ns[v-1].append(u-1)

bs = {}
cump0 = defaultdict(list)
cump1 = defaultdict(list)
def sub(u, p):
    if (p,u) in bs:
        return bs[p,u]
    b = 1
    ps = []
    for v in ns[u]:
        if v==p:
            continue
        bb = sub(v, u)
        b *= (1+bb)
        b %= M
        ps.append(bb)
    v0 = 1
    v1 = 1
    l = len(ps)
    for i in range(l):
        cump0[u].append(v0)
        cump1[u].append(v1)
        v0 *= ps[i]+1
        v1 *= ps[l-1-i]+1
        v0%=M;v1%=M
    cump0[u].append(v0)
    cump1[u].append(v1)
        
    bs[p,u] = b % M
    return b

ans = [None]*n
def sub2(u, p):
    i = 0
    for v in ns[u]:
        if v==p:
            continue
        b1 = bs[p,u]
        b2 = bs[u,v]
        b3 = bs[u,p]
        if p>=0:
            bb = (cump0[u][i] * cump1[u][-(i+2)] * (1+b3)) % M
        else:
            bb = (cump0[u][i] * cump1[u][-(i+2)]) % M
        bs[v,u] = bb
        ans[v] = bs[u,v] * (1+bb) % M
        sub2(v,u)
        i += 1
        
sub(0, -1)
bs[0,-1] = 1
ans[0] = bs[-1,0]
sub2(0,-1)

# for u in range(n):
#     ans[u] = sub(u, -1)[1] % M
write("\n".join(map(str, ans)))
### BUGGY CODE ###

import numpy as np
N = int(input())
L = np.array(sorted(list(map(int, input().split()))))

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        a = L[i]
        b = L[j]
        if b >= L[-1] + a:
            break
        limit_c = a + b
        idx = np.searchsorted(L, limit_c)
        ans += idx - 1 - j
print(ans)


### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = sorted(list(map(int, input().split())))

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        a = L[i]
        b = L[j]
        idx = bisect_left(L, a + b)
        ans += idx - 1 - j
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
MOD = 998244353
S = []
for _ in range(K):
    S.append(tuple(map(int, input().split())))

dp = [0] * (N + 1)
dp[1] = 1

for i in range(2, N+1):
    sum_list = [0 for L, R in S]

    j = 0
    for L, R in S:
        RR = i - L
        if RR <= 0:
            continue
        LL = max(1, i-R)
        if sum_list[j] == 0:
            t = sum(dp[LL:RR+1]) % MOD
            sum_list[j] = t
            dp[i] += t
        else:
            if LL >= 2:
                sum_list[j] -= dp[1]
            sum_list[j] += dp[RR]
            sum_list[j] %= MOD
            dp[i] += sum_list[j]
        j += 1

    dp[i] %= MOD

print(dp[N])


### FIXED CODE ###

N, K = map(int, input().split())
MOD = 998244353
S = []
for _ in range(K):
    S.append(tuple(map(int, input().split())))

dp = [0] * (N + 1)
dp[1] = 1
sum_list = [0] * (N + 1)
sum_list[1] = 1

for i in range(2, N+1):
    for L, R in S:
        RR = i - L
        if RR <= 0:
            continue
        LL = max(1, i-R)
        if LL <= RR:
            t = sum_list[RR] - sum_list[LL-1]
            dp[i] += t
    sum_list[i] = (sum_list[i-1] + dp[i]) % MOD
    dp[i] %= MOD

print(dp[N])
### BUGGY CODE ###

# coding: utf-8
# Your code here!
N=int(input())

lr=[]
ma=0
for _ in range(N):
    l,r=map(int,input().split())
    ma=max(l,r,ma)
    lr.append([l,r])

#print(ma)

l=[0]*(ma+1)

for n in range(3,ma+1)[::2]:
    temp=(n*(n+1))//2
    flag=True
    for i in range(2,-int(-temp**0.5//1)):
        if temp%i==0:
            if i!=(n+1)//2:
                #print(n,i)
                flag=False
                break
    if flag:
        l[n]=l[n-2]+1
    else:
        l[n]=l[n-2]

#print(l)
for item in lr:
    print(l[item[1]]-l[item[0]] if l[item[0]-2]==l[item[0]] or item[0]==1 else l[item[1]]-l[item[0]]+1)
    


### FIXED CODE ###

# coding: utf-8
# Your code here!
N=int(input())

lr=[]
ma=0
for _ in range(N):
    l,r=map(int,input().split())
    ma=max(l,r,ma)
    lr.append([l,r])

#print(ma)

l=[0]*(ma+1)

for n in range(3,ma+1)[::2]:
    temp=(n*(n+1))//2
    flag=True
    for i in range(2,-int(-temp**0.5//1)):
        if temp%i==0:
            if i!=(n+1)//2:
                #print(n,i)
                flag=False
                break
    if flag:
        l[n]=l[n-2]+1
    else:
        l[n]=l[n-2]

#print(l)
for item in lr:
    print(l[item[1]]-l[item[0]] if l[item[0]-2]==l[item[0]] or item[0]==1 else l[item[1]]-l[item[0]]+1)
### BUGGY CODE ###

n = int(input())

ans = 1

for i in range(1,n+1):
  ans = ans*i
print(ans%((10**9)+7))


### FIXED CODE ###

n = int(input())

ans = 1

for i in range(1,n+1):
  ans = (ans*i)%((10**9)+7)
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
import itertools
ans = 0
result = []


def listExcludedIndices(data, indices=[]):
  return [x for i, x in enumerate(data) if i not in indices]

for i in range(len(a)):
  for j in range(i, len(a) - 1):
      jData = listExcludedIndices(a, [i])
      #result.append([a[i], jData[j]])
      ans += a[i] * jData[j]

print(ans%(10 ** 9 + 7))

### FIXED CODE ###

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

ans = 0

sum_a = sum(a)


for i in range(n):
    ans += a[i] * (sum_a - a[i])
    sum_a -= a[i]

print(ans%(10 ** 9 + 7))
### BUGGY CODE ###

def c_4_over_n(N):
    for h in range(1, 3501):
        for n in range(1, 3501):
            # 条件式をwについて整理したときの分子と分母
            numerator = N * h * n
            denominator = 4 * h * n - N * n - N * h
            if denominator > 0 and numerator % denominator == 0:
                w = numerator // denominator
            else:
                continue
            if 1 <= w <= 3500:
                ans = '{0} {1} {2}'.format(h, n, w)
                return ans
    return None

N = int(input())
print(c_4_over_n(N))

### FIXED CODE ###

def c_4_over_n(N):
    for h in range(1, 3501):
        for n in range(1, h + 1):
            # 条件式をwについて整理したときの分子と分母
            numerator = N * h * n
            denominator = 4 * h * n - N * n - N * h
            # このときwが正整数になる
            if denominator > 0 and numerator % denominator == 0:
                w = numerator // denominator
                # 分母の値が小さなもの順に表示する(趣味)
                ans = '{0} {1} {2}'.format(*sorted([h, n, w]))
                return ans
    return None

N = int(input())
print(c_4_over_n(N))
### BUGGY CODE ###

S = input()[::-1]
mod = 1000000007

n = len(S)
a = S[0]
dp = [0] * 26
l = [[13 - i * j % 13 for j in range(1, 10)] for i in [1, 10, 9, 12, 3, 4]] * (n // 6 + 1)
if a == "?":
    dp[0:10] = [1] * 10
else:
    dp[int(a)] = 1
for s, l_ in zip(S[1:], l[1:]):
    dp[13:] = dp[:13]
    if s == "?":
        x = dp[:13]
        for v in l_:
            for i, x_ in enumerate(dp[v:v+13]):
                x[i] += x_
        dp[:13] = x
    else:
        if s != "0":
            v = l_[int(s) - 1]
            dp[:13] = dp[v:v+13]
#     x %= mod
print(dp[5] % mod)

### FIXED CODE ###

#!python3

LI = lambda: list(map(int, input().split()))

# input
S = input()

MOD = 10 ** 9 + 7


def main():
    n = len(S)
    m = 5
    w = []
    p = 1
    for i in range(n):
        s = S[-1 - i]
        if s == "?":
            w.append(p)
        else:
            m = (m - int(s) * p) % 13
        p = p * 10 % 13

    n = len(w)
    l1 = [0] * 13
    l1[0] = 1
    for i in range(1, n + 1):
        l2 = [0] * 13
        for j in range(10):
            x = w[i - 1] * j % 13
            for k in range(13):
                t = (x + k) % 13
                l2[t] += l1[k]
        l1 = [y % MOD for y in l2]
    
    ans = l1[m]
    print(ans)


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

n=int(input())
h=list(map(int,input().split()))
count=0
for i in range(n-1):
    temp=0
    for j in range(n-i-1):
        if h[i+j]>=h[i+j+1]:
            temp+=1
        else: break
    count=max(count,temp)
print(count)


### FIXED CODE ###

import bisect
n=int(input())
h=list(map(int,input().split()))

count=0
temp=0
for i in range(n-1):
    if h[i]>=h[i+1]:
        temp+=1
        count=max(count,temp)
    else:
        temp=0

print(count)
### BUGGY CODE ###

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

count = [0 for i in range(N)]

for i in range(N):
    for j in range(N):
        if j < i and S[j] == "W":
            count[i] += 1
        elif j > i and S[j] == "E":
            count[i] += 1
        else:
            pass


print(min(count))

### FIXED CODE ###

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

wcount = [0 for i in range(N)]
ecount = [0 for i in range(N)]
sumcount = [0 for i in range(N)]

for i in range(1,N):
    if i == 0:
        continue
    elif i > 0 and S[i-1] == "W":
        wcount[i] = wcount[i-1] + 1
    elif i > 0:
        wcount[i] = wcount[i-1]
 
for i in reversed(range(N)):
    if i == N:
        continue
    elif i < N-1 and S[i+1] == "E":
        ecount[i] = ecount[i+1] + 1
    elif i < N-1:
        ecount[i] = ecount[i+1]
    

for i in range(N):
    sumcount[i] = wcount[i] + ecount[i]

print(min(sumcount))
### BUGGY CODE ###

from collections import Counter
import heapq

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

word_count=Counter(word)

ans=[k for k, v in word_count.items() if v == max(word_count.values())]
cnt=len(ans)
heapq.heapify(ans)
for i in range(cnt):
    print(heapq.heappop(ans))


### FIXED CODE ###

from collections import Counter
import heapq

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

word_count=Counter(word)
ma=max(word_count.values())

ans=[k for k, v in word_count.items() if v == ma]
cnt=len(ans)
heapq.heapify(ans)
for i in range(cnt):
    print(heapq.heappop(ans))
### BUGGY CODE ###

import numpy as np
from itertools import product
H, W, K = map(int, input().split())
G = np.array([list(map(int, list(input()))) for _ in range(H)])

ans = float("inf")

for pattern in product([0, 1], repeat = H - 1):
    div = [0] + [i for i, p in enumerate(pattern, 1) if p == 1] + [20]
    rows = []
    for i in range(len(div) - 1):
        rows.append(np.sum(G[div[i]: div[i + 1]], axis=0)) # 列方向
    

    if [r for r in rows if np.any(r > K)]:
        continue

    tmp_ans = 0
    cnt = [0] * len(rows)
    w = 0
    rows = [r.tolist() for r in rows]

    while w < W:
        for r in range(len(rows)):
            cnt[r] += rows[r][w]
        if np.any(np.array(cnt) > K):
            cnt = [0] * len(rows)
            tmp_ans += 1
            w -= 1
        w += 1
    
    tmp_ans += pattern.count(1)
    ans = min(ans, tmp_ans)

print(ans)

### FIXED CODE ###

from itertools import product
H, W, K = map(int, input().split())
G = [list(map(int, list(input()))) for _ in range(H)]

ans = float("inf")

for pattern in product([0, 1], repeat = H - 1):
    div = [0] + [i for i, p in enumerate(pattern, 1) if p == 1] + [H]
    rows = []
    for i in range(len(div) - 1):
        row = []
        for j in range(W):
            tmp = 0
            for k in range(div[i], div[i + 1]):
                tmp += G[k][j]
            row.append(tmp)
        rows.append(row)
        
    flag = True
    for row in rows:
        if [r for r in row if r > K]:
            flag = False
            break
    if not flag:
        continue

    tmp_ans = 0
    cnt = [0] * len(rows)
    w = 0

    while w < W:
        for r in range(len(rows)):
            cnt[r] += rows[r][w]
        if [c for c in cnt if c > K]:
            cnt = [0] * len(rows)
            tmp_ans += 1
            w -= 1
        w += 1
    
    tmp_ans += pattern.count(1)
    ans = min(ans, tmp_ans)

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

import sys
input = sys.stdin.readline

H, W, D = map(int, input().split())
L = [[int(v) - 1 for v in input().split()] for _ in range(H)]
Q = int(input())
QL = [[int(v) - 1 for v in input().split()] for _ in range(Q)]

m = [None] * (H * W)
for i in range(H):
    for j in range(W):
        m[L[i][j]] = (i, j)

dp = [None] * (H * W)
for i in range(D):
    dp[i] = 0
    for j in range(i + D, H * W, D):
        x, y = m[j - D]
        nx, ny = m[j]
        
        dp[j] = abs(x - nx) + abs(y - ny)

for qx, qy in QL:
    ans = 0
    for q in range(qx + D, qy + D, D):
        ans += dp[q]
    print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

H, W, D = map(int, input().split())
L = [[int(v) - 1 for v in input().split()] for _ in range(H)]
Q = int(input())
QL = [[int(v) - 1 for v in input().split()] for _ in range(Q)]

m = [None] * (H * W)
for i in range(H):
    for j in range(W):
        m[L[i][j]] = (i, j)

dp = [None] * (H * W)
for i in range(D):
    dp[i] = 0
    for j in range(i + D, H * W, D):
        x, y = m[j - D]
        nx, ny = m[j]
        
        dp[j] = dp[j - D] + abs(x - nx) + abs(y - ny)

for qx, qy in QL:
    print(dp[qy] - dp[qx])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from heapq import heappop, heappush

N = int(input())
INF = float("inf")
d = [INF for n in range(N)]
d[0] = 0
adj = [[] for _ in range(N)]

for n in range(N):
    inp = tuple(map(int, input().split()))
    for i in range(inp[1]):
        adj[n] = list(zip(inp[2::2], inp[3::2]))

heap = [[0, 0]]

while len(heap):
    pcost, p = heappop(heap)
    
    for v, c in adj[p]:
        new_cost = pcost + c
        if new_cost < d[v]:
            d[v] = new_cost
            heappush(heap, [new_cost, v])

for n in range(N):
    print("{} {}".format(n, d[n]))

### FIXED CODE ###

# -*- coding: utf-8 -*-
from heapq import heappop, heappush
def inpl(): return list(map(int, input().split()))
INF = float("inf")
N = int(input())
G = []
for _ in range(N):
    I = inpl()
    G.append(zip(*[I[3::2], I[2::2]]))

def dijkstra(G):
    C = [INF]*(N)
    C[0] = 0
    visited = [False] * (N)
    Q = [[0, 0]]

    while Q:
        c, u = heappop(Q)
        if C[u] < c:
            continue
        visited[u] = True
        for d, v in G[u]:
            if visited[v]:
                continue
            e = c + d
            if e < C[v]:
                C[v] = e
                heappush(Q, [e, v])
    return C

for i, c in enumerate(dijkstra(G)):
    print(i, c)
### BUGGY CODE ###

from statistics import median

n = int(input())
x = [int(i) for i in input().split()]

for i in range(n):
    print(median(x[:i] + x[i+1:]))

### FIXED CODE ###

n = int(input())
x = [int(i) for i in input().split()]

sorted_x = sorted(x)
smaller = sorted_x[n//2 - 1]
bigger = sorted_x[n//2]

for i in range(n):
    print(bigger if x[i] <= smaller else smaller)
### BUGGY CODE ###

n = int(input())
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)
ans = 0
for ai in a:
    for bi in b:
        if bi <= ai:
            break
        for ci in c:
            if ci <= bi:
                break
            ans += 1
print(ans)

### FIXED CODE ###

import bisect

n = int(input())
a = sorted(list(map(int, input().split())))
b = sorted(list(map(int, input().split())))
c = sorted(list(map(int, input().split())))
ans = 0
for bi in b:
    upper = bisect.bisect_left(a, bi)
    lower = n - bisect.bisect_right(c, bi)
    ans += upper * lower
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
a=0
b=0

for i in range(n-k+1):
    if sum(p[i:i+k]) >= a:
        a=sum(p[i:i+k]) 
        b=i

print(sum([(k+1)/2 for k in p[b:b+k]]))

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
a=0
for i in range(n-k+1):
    if i==0:
        xe=sum(p[0:k])
    else:
        xe=xe-p[i-1]+p[i+k-1]
    a=max(a,xe)
print((k+a)/2)
### BUGGY CODE ###

# 2019/12/27

h,w=map(int,input().split())
s=[list('#'*(w+2))]
for _ in range(h):
    s+=[list('#'+input()+'#')]
s+=[list('#'*(w+2))]

# G=[[[0]*4]*(w+2) for _ in range(h+2)] #[L,U,R,D]
G=[]
for i in range(h+2):
    g=[]
    for j in range(w+2):
        g.append([0,0,0,0])
    G.append(g)
L,U,R,D=list(range(4))

for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]=="#":continue
        G[i][j][L]=G[i][j-1][L]+1
        G[i][j][U]=G[i-1][j][U]+1
        
ans=0

for i in range(h,0,-1):
    for j in range(w,0,-1):
        if s[i][j]=="#":continue
        G[i][j][R]=G[i][j+1][R]+1
        G[i][j][D]=G[i+1][j][D]+1
        lit=sum(G[i][j])-3
        ans=max(ans,lit)
print(ans)

### FIXED CODE ###

# 2019/12/27

h,w=map(int,input().split())
s=[list('#'*(w+2))]
for _ in range(h):
    s+=[list('#'+input()+'#')]
s+=[list('#'*(w+2))]

L,U,R,D=[[[0]*(w+2) for _ in range(h+2)] for _ in range(4)]

for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]=="#":continue
        L[i][j]=L[i][j-1]+1
        U[i][j]=U[i-1][j]+1

ans=0

for i in range(h,0,-1):
    for j in range(w,0,-1):
        if s[i][j]=="#":continue
        R[i][j]=R[i][j+1]+1
        D[i][j]=D[i+1][j]+1
        lit=L[i][j]+U[i][j]+R[i][j]+D[i][j]-3
        ans=max(ans,lit)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, ma, mb = map(int,input().split())
A = [0]*n
B = [0]*n
C = [0]*n
for i in range(n) :
    A[i], B[i], C[i] = map(int,input().split())

INF = 10**9

# dp[i][ca][cb] := i番目までの(ca, cb)の最小費用
dp = [[[INF]*401 for j in range(401)] for i in range(n+1)]

dp[0][0][0] = 0
for i in range(1, n+1) :
    dp[i][A[i-1]][B[i-1]] = C[i-1]

for i in range(1, n+1) :
    for ca in range(1, 401) :
        for cb in range(1, 401) :
            if not (ca-A[i-1] >= 0 and cb-B[i-1] >= 0) :
                dp[i][ca][cb] = min(dp[i][ca][cb], dp[i-1][ca][cb])
            else :
                dp[i][ca][cb] = min(dp[i][ca][cb], dp[i-1][ca][cb], dp[i-1][ca-A[i-1]][cb-B[i-1]]+C[i-1])

ans = INF

for ca in range(1, 401) :
    for cb in range(1, 401) :
        if mb*ca == ma*cb :
            ans = min(ans, dp[n][ca][cb])

if ans == INF :
    ans = -1

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n, ma, mb = map(int,input().split())
A = [0]*n
B = [0]*n
C = [0]*n
for i in range(n) :
    A[i], B[i], C[i] = map(int,input().split())

INF = 10**9

# dp[i][ca][cb] := i番目までの(ca, cb)の最小費用
dp = [[[INF]*401 for j in range(401)] for i in range(n+1)]

dp[0][0][0] = 0
for i in range(1, n+1) :
    dp[i][A[i-1]][B[i-1]] = C[i-1]

for i in range(1, n+1) :
    for ca in range(1, 401) :
        for cb in range(1, 401) :
            if not (ca-A[i-1] >= 0 and cb-B[i-1] >= 0) :
                dp[i][ca][cb] = min(dp[i][ca][cb], dp[i-1][ca][cb])
            else :
                dp[i][ca][cb] = min(dp[i][ca][cb], dp[i-1][ca][cb], dp[i-1][ca-A[i-1]][cb-B[i-1]]+C[i-1])

ans = INF

for ca in range(1, 401) :
    for cb in range(1, 401) :
        if mb*ca == ma*cb :
            ans = min(ans, dp[n][ca][cb])

if ans == INF :
    ans = -1

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

N,M = list(map(int,input().split()))
Map = [[] for i in range(N)]
for i in range(M):
    a,b=list(map(int,input().split()))
    Map[a-1].append(b-1)

b_list = []
count=0   
for i in range(N):
    if i in b_list:
       b_list=[]
       count+=1
    b_list=b_list+Map[i]

print(count)

### FIXED CODE ###


N,M = list(map(int,input().split()))
Map = [[] for i in range(N)]
for i in range(M):
    a,b=list(map(int,input().split()))
    Map[a-1].append(b-1)

b_list = [0 for i in range(N)]
count=0   
for i in range(N):
    if b_list[i]==1:
        b_list=[0 for i in range(N)]
        count+=1
    for j in Map[i]:
        b_list[j]=1

print(count)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
B=[]
for k in range(N):
    B.append([A[k],k+1])
B.sort(key=lambda x: x[0], reverse=True)
dp=[[0 for k in range(N+1)]for k in range(N+1)]

for k in range(N):
    for j in range(k+1):
        if k>j:
            dp[j+1][k-j]=max(dp[j][k-j]+B[k][0]*(B[k][1]-j-1), dp[j+1][k-j-1]+B[k][0]*(N-k+j+1-B[k][1]))
        if k==j:
            dp[j+1][0]=dp[j][0]+B[k][0]*(B[k][1]-j-1)
        if j >0:
            dp[j][k-j+1]=max(dp[j-1][k-j+1]+B[k][0]*(B[k][1]-j), dp[j][k-j]+B[k][0]*(N-k+j-B[k][1]))
        if j==0:
            dp[0][k-j+1]=dp[0][k-j]+B[k][0]*(N-k+j-B[k][1])
ans=[]
for k in range(N+1):
    ans.append(dp[k][N-k])
print(max(ans))               

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=[]
for k in range(N):
    B.append([A[k],k+1])
B.sort(key=lambda x: x[0], reverse=True)
dp=[[0 for k in range(N+1)]for k in range(N+1)]
dp[1][0]=dp[0][0]+B[0][0]*(B[0][1]-1)
dp[0][1]=dp[0][0]+B[0][0]*(N-B[0][1])
for k in range(1,N):
    #j=0
    dp[0][k+1]=dp[0][k]+B[k][0]*(N-k-B[k][1])
    dp[1][k]=max(dp[0][k]+B[k][0]*(B[k][1]-1), dp[1][k-1]+B[k][0]*(N-k+1-B[k][1]))
    #j=k
    dp[k+1][0]=dp[k][0]+B[k][0]*(B[k][1]-k-1)
    dp[k][1]=max(dp[k-1][+1]+B[k][0]*(B[k][1]-k), dp[k][0]+B[k][0]*(N-B[k][1]))
    for j in range(1,k):
        dp[j+1][k-j]=max(dp[j][k-j]+B[k][0]*(B[k][1]-j-1), dp[j+1][k-j-1]+B[k][0]*(N-k+j+1-B[k][1]))
        dp[j][k-j+1]=max(dp[j-1][k-j+1]+B[k][0]*(B[k][1]-j), dp[j][k-j]+B[k][0]*(N-k+j-B[k][1]))
ans=[]
for k in range(N+1):
    ans.append(dp[k][N-k])
print(max(ans))
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))

INF = 10 ** 9
dp = [INF] * N
dp[0] = 0
dp[1] = abs(h[1] - h[0])

for i in range(2, N):
    for j in range(1, K + 1):
        if dp[i] > dp[i - j] + abs(h[i] - h[i - j]):
            dp[i] = dp[i - j] + abs(h[i] - h[i - j])

print(dp[-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))

INF = 10 ** 9
dp = [INF] * N
dp[0] = 0
dp[1] = abs(h[1] - h[0])

def chmin(a, b):
    if a > b:
        return b
    else:
        return a
        
for i in range(2, N):
    for j in range(1, K + 1):
        dp[i] = chmin(dp[i], dp[i - j] + abs(h[i] - h[i - j]))

print(dp[-1])