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

import sys
input = sys.stdin.readline
from collections import Counter
import itertools
from functools import lru_cache

mask = (1 << 10) - 1

@lru_cache(None)
def encode(a,b,c,d):
    t = 1 << 40
    for x,y,z,w in [(a,b,c,d), (b,c,d,a), (c,d,a,b), (d,a,b,c)]:
        u = x + (y << 10) + (z << 20) + (w << 30)
        if t > u:
            t = u
    return t

@lru_cache(None)
def decode(x):
    return [(x >> n) &mask for n in [0,10,20,30]]

@lru_cache(None)
def P(n,k):
    x = 1
    for i in range(k):
        x *= (n-i)
    return x

@lru_cache(None)
def symmetry(tile):
    a,b,c,d = decode(tile)
    if a == b == c == d:
        return 4
    if a == c and b == d:
        return 2
    return 1

N = int(input())
tiles = []
for _ in range(N):
    a,b,c,d = map(int,input().split())
    tiles.append(encode(a,b,c,d))
counter = Counter(tiles)

answer = 0
for bottom, top in itertools.combinations(tiles,2):
    counter[bottom] -= 1
    counter[top] -= 1
    a,b,c,d = decode(bottom)
    e,f,g,h = decode(top)
    for x,y,z,w in [(e,f,g,h), (f,g,h,e), (g,h,e,f), (h,e,f,g)]:
        # a,b,c,d
        # x,w,z,y 
        tiles = [encode(p,q,r,s) for p,q,r,s in [(b,a,x,w), (c,b,w,z), (d,c,z,y), (a,d,y,x)]]
        need = Counter(tiles)
        x = 1
        for tile, cnt in need.items():
            x *= P(counter[tile],cnt) # 残っている個数、必要枚数
            x *= pow(symmetry(tile), cnt)
        answer += x
    counter[bottom] += 1
    counter[top] += 1

# 上下を固定した分
answer //= 3
print(answer)

### FIXED CODE ###

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

mask = (1 << 10) - 1

def encode(a,b,c,d):
    t = 1 << 40
    for x,y,z,w in [(a,b,c,d), (b,c,d,a), (c,d,a,b), (d,a,b,c)]:
        u = x + (y << 10) + (z << 20) + (w << 30)
        if t > u:
            t = u
    return t

def decode(x):
    for _ in range(4):
        yield x & mask
        x >>= 10

def P(n,k):
    x = 1
    for i in range(k):
        x *= (n-i)
    return x

def symmetry(tile):
    a,b,c,d = decode(tile)
    if a == b == c == d:
        return 4
    if a == c and b == d:
        return 2
    return 1

N = int(input())
tiles = []
for _ in range(N):
    a,b,c,d = map(int,input().split())
    tiles.append(encode(a,b,c,d))
counter = Counter(tiles)

counter

answer = 0
for bottom, top in itertools.combinations(tiles,2):
    counter[bottom] -= 1
    counter[top] -= 1
    a,b,c,d = decode(bottom)
    e,f,g,h = decode(top)
    for x,y,z,w in [(e,f,g,h), (f,g,h,e), (g,h,e,f), (h,e,f,g)]:
        # a,b,c,d
        # x,w,z,y 
        tiles = [encode(p,q,r,s) for p,q,r,s in [(b,a,x,w), (c,b,w,z), (d,c,z,y), (a,d,y,x)]]
        need = Counter(tiles)
        x = 1
        for tile, cnt in need.items():
            x *= P(counter[tile],cnt) # 残っている個数、必要枚数
            x *= pow(symmetry(tile), cnt)
        answer += x
    counter[bottom] += 1
    counter[top] += 1

# 上下を固定した分
answer //= 3
print(answer)
### BUGGY CODE ###

s=input()
t=input()
dp=[['' for i in range(len(t)+1)] for j in range(len(s)+1)]
for i in range(len(s)):
    for j in range(len(t)):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+s[i]
        else:
            a=dp[i+1][j]
            if len(dp[i][j+1])>len(dp[i+1][j]):
                a=dp[i][j+1]
            dp[i+1][j+1]=a
print(dp[len(s)][len(t)])


### FIXED CODE ###

S=input()
T=input()
dp=[[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+1
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
i=len(S)
j=len(T)
ans=""
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=S[i-1]+ans
        i-=1
        j-=1
print(ans)
### BUGGY CODE ###

import sys
N, M = map(int, input().split())

a = [int(line) for line in sys.stdin]

ans = [0] * (N + 1)

ans[0] = 1
if 1 in a:
    ans[1] = 0
else:
    ans[1] = 1
for i in range(2, N + 1):
    if i in a:
        ans[i] = 0
    else:
        ans[i] = ans[i - 1] + ans[i - 2]

print(ans[N] % 1000000007)


### FIXED CODE ###

import sys
N, M = map(int, input().split())

a = [int(line) for line in sys.stdin]

ans = [-1] * (N + 1)  # not evaluated yet

for broken in a:
    ans[broken] = 0  # unreachable

ans[0] = 1  # reachable

if ans[1]:
    ans[1] = 1

for i in range(2, N + 1):
    if ans[i]:
        ans[i] = ans[i - 1] + ans[i - 2]

print(ans[N] % 1000000007)
### BUGGY CODE ###

# coding: utf-8

from itertools import permutations
import sys

N, M, R = map(int, sys.stdin.readline().split())
r = [i - 1 for i in map(int, sys.stdin.readline().split())]

G = [[float('inf')] * N for _ in xrange(N)]

for i in xrange(N):
    G[i][i] = 0

for i in range(M):
    A, B, C = map(int, sys.stdin.readline().split())
    G[A-1][B-1] =  G[B-1][A-1] = C

# Warshall–Floyd Algorithm
for k in xrange(N):
    for i in xrange(N):
        for j in xrange(N):
            G[i][j] = min(G[i][j], G[i][k] + G[k][j]); 

ans = float('inf')

for i in permutations(r):
    ans = min(ans, sum([G[i[j]][i[j+1]] for j in xrange(R-1)]))

print ans


### FIXED CODE ###

# coding: utf-8

from itertools import permutations
import Queue

N, M, R = map(int, raw_input().split())
r = [i - 1 for i in map(int, raw_input().split())]

G = [[] for _ in xrange(N)]

for i in range(M):
    A, B, C = map(int, raw_input().split())
    A -= 1; B -= 1;
    G[A].append((B, C))
    G[B].append((A, C))

# dijkstra Algorithm
def dijkstra(s):
    d = [float("inf") for _ in xrange(N)]
    que = Queue.PriorityQueue()
    d[s] = 0
    que.put([0, s])

    while not que.empty():
        p = que.get()
        v = p[1]
        if d[v] < p[0]:
            continue
        for i, j in G[v]:
            if d[i] > d[v] + j:
                d[i] = d[v] + j
                que.put([d[i], i])
    return d

table = {}

for i in r:
    table[i] = dijkstra(i)

ans = float('inf')

for i in permutations(r):
    ans = min(ans, sum([table[i[j]][i[j+1]] for j in xrange(R-1)]))

print ans
### BUGGY CODE ###

#!/usr/bin/env python3
# O(NlogN)

n = int(input())

div = [0 for _ in range(n+1)]
for i in range(1, n+1):
    ti = i 
    while True:
        if ti > n:
            break
        div[ti] += 1 
        ti += i
ans = 0 
for i in range(1, n+1):
    ans += i*div[i]
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
# O(NlogN)

n = int(input())

div = [0 for _ in range(n+1)]
for i in range(1, n+1):
    ti = i 
    while True:
        if ti > n:
            break
        div[ti] += 1 
        ti += i
ans = 0 
for i in range(1, n+1):
    ans += i*div[i]
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())
cnt = 0
for _ in range(Q):
    q = input().split()
    if len(q) == 1:
        cnt += 1
    else:
        if cnt % 2 == 0:
            if int(q[1]) == 1:
                S = q[2] + S
            else:
                S += q[2]
        else:
            if int(q[1]) == 1:
                S += q[2]
            else:
                S = q[2] + S

if cnt % 2 == 1:
    S = S[::-1]
print(S)

### FIXED CODE ###

S = input()
Q = int(input())
cnt = 0
mae = []
usiro = []
for _ in range(Q):
    q = input().split()
    if len(q) == 1:
        cnt += 1
    else:
        if cnt % 2 == 0:
            if int(q[1]) == 1:
                mae.append(q[2])
            else:
                usiro.append(q[2])
        else:
            if int(q[1]) == 1:
                usiro.append(q[2])
            else:
                mae.append(q[2])

mae = mae[::-1]
S = "".join(mae) + S + "".join(usiro)

if cnt % 2 == 1:
    S = S[::-1]
print(S)
### BUGGY CODE ###

def main():
    n, k, *h = map(int, open(0).read().split())
    dp = [float('inf')] * n
    dp[0] = 0
    for i in range(1, n):
        min_i = max(0, i-k)
        for j in range(min_i, i):
            dp[i] = min(dp[j] + abs(h[i] - h[j]), dp[i])
    print(dp[n-1])
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, k, *h = map(int, open(0).read().split())
    dp = [float('inf')] * n
    dp[0] = 0
    for i in range(1, n):
        min_i = max(0, i-k)
        dp[i] = min([dp[j] + abs(h[i] - h[j]) for j in range(min_i, i)])
    print(dp[n-1])
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import math

s = input()
li = [0 for _ in range(len(s))]

for i in range(len(s)):
    if s[i] == "R":
        t = s[i:].index("L")
        if t % 2 != 0:
            li[i + t - 1] += 1
        else:
            li[i + t] += 1
    else:
        t = s[:i].rfind("R")
        if (i - t) % 2 != 0:
            li[t + 1] += 1
        else:
            li[t] += 1

print(*li)

### FIXED CODE ###

import math

s = input()
li = [0 for _ in range(len(s))]

for i in range(len(s)):
    if s[i] == "R":
        t = s[i:].index("L")
        if t % 2 != 0:
            li[i + t - 1] += 1
        else:
            li[i + t] += 1
    else:
        t = s[:i].rfind("R")
        if (i - t) % 2 != 0:
            li[t + 1] += 1
        else:
            li[t] += 1

print(*li)
### BUGGY CODE ###

k,s = map(int,input().split())
k=k+1
count=0
for i in range(k):
    for j in range(k):
        if i+j > s:
            break
        for m in range(k):
            if i+j+m > s:
                break
            if i+j+m == s:
                count = count+1
            #print(i," ",j," ",m)

print(count)

### FIXED CODE ###

k,s = map(int,input().split())
k=k+1
count=0
for i in range(k):
    for j in range(k):
        if i+j > s:
            break
        m = s - (i+j)
        if m >= 0 and m < k:
            count = count+1
        #print(i," ",j," ",m)

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

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

import collections
c = collections.Counter(a_list)

dict_items = list(c.items())

for i in range(n): # kごと
    ans_i = 0
    for j in range(len(dict_items)):
        if a_list[i] == dict_items[j][0]:
            ans_i += ((dict_items[j][1] - 1) * (dict_items[j][1] - 2)) / 2
        else:
            ans_i += ((dict_items[j][1] - 0) * (dict_items[j][1] - 1)) / 2
    print(int(ans_i))

### FIXED CODE ###

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

import collections
c = collections.Counter(a_list)

dict_items = list(c.items())

ans_max = 0
for j in range(len(dict_items)):
    ans_max += ((dict_items[j][1] - 0) * (dict_items[j][1] - 1)) / 2
    
for i in range(n): # kごと
    tmp = c[a_list[i]]
    ans_tmp = ans_max - tmp*(tmp-1)/2 + (tmp-1)*(tmp-2)/2
    print(int(ans_tmp))
### BUGGY CODE ###

k, s = map(int, input().split())
count = 0
for x in range(k+1):
    if(x > s):
        continue
    for y in range(k+1):
        if(x + y > s):
            continue
        for z in range(k+1):
            if (x + y + z == s):
                count = count + 1
print(count)

### FIXED CODE ###

k, s = map(int, input().split())
count = 0
for x in range(k+1):
    if(x > s):
        break
    for y in range(k+1):
        if(x + y > s):
            break
        if(s - (x + y) <= k):
            count = count + 1
print(count)
### BUGGY CODE ###

s = input()
keta = len(s)
n = int(s)

ans = 0
while n > 0:
    hoge = 10 ** (keta-1)
    t = n // (hoge)
    if t == 0:
        keta -= 1
        continue

    if t < 5 or (t == 5 and ((n // (hoge//10) if hoge >= 10 else 0) <= 54)):  # 555 の時とか1000円だすと14枚で行けてしまう。。
        ans += t
        n = n - t * hoge
        keta -= 1

    else:
        ans += 1
        n = hoge*10 - n  # どちらがお金を払うかが入れ替わる

print(ans)


### FIXED CODE ###

n = input()
lenn = len(n)

dp = [0, 10000]
for d in reversed(n):
    d = int(d)
    dp = [min(d + dp[0], d + 1 + dp[1]), min(10 - d + dp[0], 9 - d + dp[1])]

print(min(dp[0], 1 + dp[1]))
### BUGGY CODE ###

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

ans = 1
for i in a: ans*=i

if ans > 1e18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

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

ans = 1
if (0 in a):
    print(0)
    exit()

for i in a:
    ans*=i
    if ans > 1e18:
        break

if ans > 1e18:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

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

for i in range(m) :
  index = a.index(max(a))
  a[index] = a[index]//2
  
print(sum(a))

### FIXED CODE ###

import heapq

n,m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n) :
  a[i] *= -1

heapq.heapify(a)
for i in range(m) :
  at = -1*(-1*heapq.heappop(a)//2)
  heapq.heappush(a, at)

print(sum(a)*-1)
### BUGGY CODE ###

import collections
N=int(input())
A=list(map(int,input().split()))
sum=0
for i in range(N):
    x=A.pop(i)
    c=collections.Counter(A)
    for j in c.values():
        sum+=j*(j-1)/2
    print(int(sum))
    sum=0
    A.insert(i,x)


### FIXED CODE ###

import collections
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=int(input())
A=list(map(int,input().split()))

c=collections.Counter(A)
list=c.values()
result=0

for x in list:
    if x>1:
        result+=cmb(x,2)
for y in c.keys():
    c[y]=result-(c[y]-1)

for z in A:
    print(c[z])
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    MAX = 10**18
    ans = a[0]
    for ai in a[1:]:
        ans *= ai
    if ans > MAX:
        print(-1)
    else:
        print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    MAX = 10**18
    if 0 in set(a):
        print(0)
    else:
        ans = a[0]
        for ai in a[1:]:
            ans *= ai
            if ans > MAX:
                print(-1)
                return
        print(ans)

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

from collections import deque

h, w = map(int, input().split())
start_h, start_w = map(int, input().split())
goal_h, goal_w = map(int, input().split())

start_h += 1
start_w += 1
goal_h += 1
goal_w += 1

s = ["#"*(w+4)]
s.append("#"*(w+4))
for _ in range(h):
    s.append("##" + input() + "##")
s.append("#"*(w+4))
s.append("#"*(w+4))

ans = [[-1]*(w+4) for _ in range(h+4)]
for i in range(h+4):
    for j in range(w+4):
        if s[i][j] == "#":
            ans[i][j] = -2
ans[start_h][start_w] = 0

move1 = [(-1, 0), (1, 0), (0, -1), (0, 1)]
move2 = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),(-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2),(0, -2), (0, -1), (0, 0), (0, 1), (0, 2),(1, -2), (1, -1), (1, 0), (1, 1), (1, 2),(2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

yet = deque([(start_h, start_w)])
done = deque()

while yet:
    x1, y1 = yet.popleft()
    done.append((x1, y1))
    for (p, q) in move1:
        v1, v2 = x1+p, y1+q
        if ans[v1][v2] == -1: 
            yet.append((v1, v2))
            ans[v1][v2] = ans[x1][y1]

    if len(yet) == 0:
        while done:
            x2, y2 = done.popleft()
            for (p, q) in move2:
                i, j = x2+p, y2+q
                if ans[i][j] == -1:
                    ans[i][j] = ans[x2][y2]+1
                    yet.append((i, j))

print(ans[goal_h][goal_w])


### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
start_h, start_w = map(int, input().split())
goal_h, goal_w = map(int, input().split())

start_h += 1
start_w += 1
goal_h += 1
goal_w += 1

s = ["#"*(w+4)]
s.append("#"*(w+4))
for _ in range(h):
    s.append("##" + input() + "##")
s.append("#"*(w+4))
s.append("#"*(w+4))

ans = [[-1]*(w+4) for _ in range(h+4)]
for i in range(h+4):
    for j in range(w+4):
        if s[i][j] == "#":
            ans[i][j] = -2
ans[start_h][start_w] = 0

move1 = [(-1, 0), (1, 0), (0, -1), (0, 1)]
move2 = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),(-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2),(0, -2), (0, -1), (0, 0), (0, 1), (0, 2),(1, -2), (1, -1), (1, 0), (1, 1), (1, 2),(2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

yet = deque([(start_h, start_w)])
done = deque()

while len(yet) > 0:
    x1, y1 = yet.popleft()
    done.append((x1, y1))
    for (p, q) in move1:
        v1, v2 = x1+p, y1+q
        if ans[v1][v2] == -1: #"."でまだ辿り着いていないマス
            yet.append((v1, v2))
            ans[v1][v2] = ans[x1][y1]

    if len(yet) == 0:
        while len(done) > 0:
            x2, y2 = done.popleft()
            for (p, q) in move2:
                i, j = x2+p, y2+q
                if ans[i][j] == -1:
                    ans[i][j] = ans[x2][y2]+1
                    yet.append((i, j))

print(ans[goal_h][goal_w])
### BUGGY CODE ###

N,K = map(int,input().split())
s = input()
lista = []
if s[0] == '0':
    lista.append(0)
now = s[0]
count = 0
for i in s:
    if now == i:
        count += 1
    else:
        lista.append(count)
        count = 1
        now = i
lista.append(count)
ans = 0
for i in range(0,len(lista),2):
    ans= max(ans,sum(lista[i:i+2*K+1]))
for i in range(1,len(lista),2):
    ans= max(ans,sum(lista[i:i+2*K]))
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
s=input()
if '0' not in s:
    print(len(s))
else:
    s2 = [0]
    count = 0
    for i in range(len(s)-1):
        count += 1
        if s[i] != s[i+1]:
            s2.append(count)
    s2.append(count+1)
    if s[0] == '0':
        s2.insert(0,0)
    ans = 0
    for i in range(0,len(s2)-1,2):
        ans = max(ans,s2[min(len(s2)-1,i+2*K+1)] - s2[i])
    print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200010)
def input():
    return sys.stdin.readline()[:-1]

def main():
    N, M = list(map(int,input().split()))
    G = [[] for k in range(N)]
    for i in range(M):
        A, B = list(map(int,input().split()))
        G[A-1].append(B-1)
        G[B-1].append(A-1)
    for e in G[0]:
        if e in G[N-1]:
            print("POSSIBLE")
            exit(0)
    print("IMPOSSIBLE")
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
def main():
    N, M = map(int,input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int,input().split())
        G[a-1].append(b-1)
    for e in G[0]:
        if N-1 in G[e]:
            print("POSSIBLE")
            exit(0)
    print("IMPOSSIBLE")

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

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

setA = set(A)

def check(i,j):
    a = abs(i-j)
    h = A[i] + A[j]
    if a == h:
        return True
    else:
        return False

res = 0
for i in range(N):
    for j in range(i+1,N):
       if check(i,j):
           res += 1 

print(res)


### FIXED CODE ###

from collections import defaultdict

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

CNT = defaultdict(int)
ans = 0

for i, a in enumerate(A):
    ima = i-a
    if ima in CNT:
        ans += CNT[ima]

    CNT[i+a] += 1

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

def I(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
n,k = MI()
h = LI()
h = h+ [float('INF')]*10000
dp = [float('INF')]*(10**5+1000)
dp[0] = 0
for i in range(n):
  for j in range(1,k+1):
    dp[i+j] = min(dp[i+j],dp[i] + abs(h[i+j] - h[i])) 
print(dp[n-1])

### FIXED CODE ###

def I(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
n,k = MI()
h = LI()
h = h+ [float('INF')]*10000
dp = [float('INF')]*(10**5+1000)
dp[0] = 0
for i in range(n):
  for j in range(1,k+1):
    dp[i+j] = min(dp[i+j],dp[i] + abs(h[i+j] - h[i])) 
print(dp[n-1])
### BUGGY CODE ###

from  itertools import combinations

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

res = 0
for a, b, c in combinations(l, 3):
    if all([a<b+c, b<c+a, c<a+b]):
        res += 1

print(res)

### FIXED CODE ###

import bisect

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

res = (n * (n-1) * (n-2)) // 6
for i in range(n-2):
    a = l[i]
    for j in range(i+1, n-1):
        b = l[j]
        res -= n - bisect.bisect_left(l, a+b)

print(res)
### BUGGY CODE ###

n, q = map(int,input().split())
c = [0] * n
c = list(map(int,input().split()))
l = [0] * q
r = [0] * q
for i in range(q):
    l[i] , r[i] =  map(int,input().split())

for i in range(q):
    u = len(set(c[l[i]-1:r[i]]))
    print(u)

### FIXED CODE ###

def main(N,Q,C,LR,A):
    data = [0]*(N+1)
    def add(i,x):
        i+=1
        while i <= N:
            data[i]+= x
            i+=i&-i 
            #下桁から最初に1が出現するところまで拾う
            #111 -> 1 , 1100 -> 100 , 1010 -> 1
    def sum(a,b):
        r=0
        i=b
        while i>0:
            r+=data[i]
            i-=i&-i
        i=a
        while i>0:
            r-=data[i]
            i-=i&-i
        return r
    p=[-1]*N
    q=0
    a=[0]*Q
    for i in range(N):
        if p[C[i]-1]>=0:
            add(p[C[i]-1],-1)
        p[C[i]-1]=i
        add(i,1)
        while q<Q and LR[A[q]][1]==i+1:
            a[A[q]]=sum(LR[A[q]][0]-1,LR[A[q]][1])
            q+=1
    return a

import sys
if sys.argv[-1]=='ONLINE_JUDGE':
    from numba import*
    from numba.pycc import CC
    cc = CC('my_module')
  
    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return njit(f)
  
    main=cc_export(main,(i8,i8,i8[:],i8[:,:],i8[:]))
    cc.compile()
    exit()
  
def input(): return sys.stdin.buffer.readline()
N,Q=map(int, input().split())
import numpy as np
C=np.array(input().split(),dtype=np.int64)
#print(C)
LR_ = [0] * (Q*2)
for i in range(Q):
    LR_[i*2],LR_[i*2+1] = input().split()
LR=np.array(LR_, dtype=np.int64).reshape(Q,2)
#print(LR)
A=np.argsort(LR[:,1])

from my_module import main
print(*main(N,Q,C,LR,A),sep='\n')
### BUGGY CODE ###

from copy import deepcopy

def warshallfloyd(cost,V):
    INF = float("inf")
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if cost[i][k]!=INF and cost[k][j]!=INF:
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

    for i in cost:
        if float("inf") in i:
            return False
    
    return True

N,M = map(int,input().split())
edge = [[float("inf") for i in range(N)] for j in range(N)]

for _ in range(M):
    a,b = map(int,input().split())
    edge[a-1][b-1] = 1
    edge[b-1][a-1] = 1

ans = 0

for i in range(N-1):
    for j in range(i+1,N):
        if edge[i][j]:
            tmp = deepcopy(edge)
            tmp[i][j] = float("inf")
            tmp[j][i] = float("inf")
            if not warshallfloyd(tmp,N):
                ans += 1

print(ans)

### FIXED CODE ###

from copy import deepcopy
from collections import deque
from heapq import heappush, heappop


def warshallfloyd(cost,V):
    INF = float("inf")
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if cost[i][k]!=INF and cost[k][j]!=INF:
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

    for i in cost:
        if float("inf") in i:
            return False
    
    return True

N,M = map(int,input().split())
edge = [[float("inf") for i in range(N)] for j in range(N)]
ab = []
for _ in range(M):
    a,b = map(int,input().split())
    ab.append([a-1,b-1])
    edge[a-1][b-1] = 1
    edge[b-1][a-1] = 1

ans = 0

for a,b in ab:
    tmp = deepcopy(edge)
    tmp[a][b] = float("inf")
    tmp[b][a] = float("inf")
    if not warshallfloyd(tmp,N):
        ans += 1

print(ans)