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

import sys
from fractions import gcd
from collections import defaultdict
from collections import deque
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    n, m = LI()
    g = [set() for i in range(n+1)]
    new_g = [set() for i in range(n+1)]
    new_gg = [set() for i in range(n+1)]
    for i in range(m):
        u, v = LI()
        g[u].add(v)
    s, t = LI()
    for i in range(n+1):
        new = set()
        for j in g[i]:
            new = new | g[j]
        new_g[i] = new_g[i] | new

    for i in range(n+1):
        new = set()
        for j in new_g[i]:
            new = new | g[j]
        new_gg[i] = new_gg[i] | new

    last = new_gg

    Q = deque([s])
    searched = [0 for i in range(n+1)]
    searched[s] = 1
    depth = [0 for i in range(n+1)]
    while len(Q) != 0:
        v = Q.popleft()
        for i in last[v]:
            if i == t:
                depth[i] = depth[v] + 1
                print(depth[i])
                return
            if searched[i] == 0:
                depth[i] = depth[v] + 1
                Q.append(i)
                searched[i] = 1
    print(-1)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from fractions import gcd
from collections import defaultdict
from collections import deque
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    n, m = LI()
    g = [[] for i in range(3*(n+1))]
    for i in range(m):
        u, v = LI()
        g[u].append(v + n + 1)
        g[u + n + 1].append(v + 2*(n + 1))
        g[u + 2*(n + 1)].append(v)

    s, t = LI()

    Q = deque([s])
    searched = [0 for i in range(3*(n+1))]
    searched[s] = 1
    depth = [0 for i in range(3*(n+1))]
    while len(Q) != 0:
        v = Q.popleft()
        for i in g[v]:
            if i == t:
                depth[i] = depth[v] + 1
                print(depth[i]//3)
                return
            if searched[i] == 0:
                depth[i] = depth[v] + 1
                Q.append(i)
                searched[i] = 1
    print(-1)


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

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

for i in range(1,len(A)+2):
    print(A.count(i))
    

### FIXED CODE ###

import collections

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

for i in range(1,len(A)+2):
    print(a[i])
### BUGGY CODE ###

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

a = list(enumerate(a))
a.sort(key = lambda x: x[1], reverse=True)

a = [list(a[i]) for i in range(n)]
a = [[a[i][0]+1, a[i][1]] for i in range(n)]

DP = [[0 for i in range(n+1)] for j in range(n+1)]
DP[0][0] = 0
for i in range(1, n+1):
    DP[0][i] = DP[0][i-1] + abs(a[i-1][1] * (n - i + 1 - a[i-1][0]))
    DP[i][0] = DP[i-1][0] + abs(a[i-1][1] * (a[i-1][0] - i))
    for x in range(1, i):
        y = i - x
        DP[x][y] = max(DP[x-1][y] + abs(a[i-1][1] * (a[i-1][0] - x)),  \
            DP[x][y-1] + abs(a[i-1][1] * (n - y + 1 - a[i-1][0])))

ans = 0
for i in range(n+1):
    ans = max(ans, DP[i][n-i])

print(ans) 

### FIXED CODE ###

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

a = list(enumerate(a))
a.sort(key = lambda x: x[1])

DP = [[0 for i in range(n+1)] for j in range(n+1)]
DP[0][0] = 0
for i in range(1, n+1):
    pos, val = a.pop()
    pos = pos + 1

    DP[0][i] = DP[0][i-1] + abs(val * (n - i + 1 - pos))
    DP[i][0] = DP[i-1][0] + abs(val * (pos - i))
    for x in range(1, i):
        y = i - x
        DP[x][y] = max(DP[x-1][y] + abs(val * (pos - x)),  \
            DP[x][y-1] + abs(val * (n - y + 1 - pos)))

ans = 0
for i in range(n+1):
    ans = max(ans, DP[i][n-i])

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

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

def largest(a,b,c):
  if a <= b:
    if a<= c:
      return a
    else:
      return c
  else:
    if b<=c:
      return b
    else:
      return c
    
def absol(d):
  if d < 0:
    return -d
  else:
    return d
    
def dist(i,j):
  return largest(j-i, absol(x-i) + absol(y-j) + 1, absol(x-j) + absol(y-i) + 1)

listlist = [0]*(n-1)

for i in range(1,n):
  for j in range(i+1,n+1):
    distance = dist(i,j)
    listlist[distance-1] = listlist[distance-1] + 1
    
for k in listlist:
  print(k)


### FIXED CODE ###

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

def dist(i,j):
  return min(j-i, abs(x-i) + abs(y-j) + 1, abs(x-j) + abs(y-i) + 1)

listlist = [0]*(n-1)

for i in range(1,n):
  for j in range(i+1,n+1):
    distance = dist(i,j)
    listlist[distance-1] = listlist[distance-1] + 1
    
for k in listlist:
  print(k)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()

def counter(L, R):
    c = 0
    for i in range(L, R):
        if s[i:i + 2] == "AC":
            c += 1
            i +=1
    return c

for i in range(q):
    l, r = map(int, input().split())
    print(counter(l - 1, r - 1))


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
t = [0] * n
for i in range(1, n):
    t[i] = t[i - 1] + (1 if s[i - 1:i + 1] == "AC" else 0)
for i in range(q):
    l, r = map(int, input().split())
    print(t[r - 1] - t[l - 1])
### BUGGY CODE ###

N, W = map(int, input().split())
items = []

for _ in range(N):
    w, v = map(int, input().split())
    items.append((w, v))

def solve(items, w=W, cur_item=0):
    if cur_item >= len(items):
        return 0
    
    cur_w, cur_v = items[cur_item]

    dont_take = solve(items, w, cur_item+1)

    if cur_w <= w:
        take = solve(items, w-cur_w, cur_item+1) + cur_v
    else:
        take = 0
    
    return max(take, dont_take)
        
print(solve(items, W))

### FIXED CODE ###

N, W = map(int, input().split())
weights, values = [], []
for _ in range(N):
    w, v = map(int, input().split())
    weights.append(w)
    values.append(v)

def solve(n, w ,weights, values):
    def rec_solve(cw, cv, max_w, i):
        nonlocal weights, values
        #print(cw, cv, i)
        if i == -1:
            return cv
        
        # take
        if weights[i] + cw <= max_w:
            return max(rec_solve(cw+weights[i], cv + values[i], max_w, i-1),
                        rec_solve(cw, cv, max_w, i-1))

        else:
            # dont take
            return rec_solve(cw, cv, max_w, i-1)

    return rec_solve(0, 0, w, n-1)

def solve_fast(n_items, max_w, weights, values):
    dp =  [[0]*(max_w+1) for _ in range(n_items)]
    dp[0] = [values[0] if i >= weights[0] else 0 for i in range(max_w+1)]

    for r in range(1, n_items):
        cw, cv = weights[r], values[r]
        for c in range(max_w+1):
            if cw > c:
                dp[r][c] = dp[r-1][c]
            else:
                dp[r][c] = max(dp[r-1][c], dp[r-1][c-cw] + cv)

    #for r in dp:
        #print(r)

    return dp[-1][-1]


print(solve_fast(N, W, weights, values))
### BUGGY CODE ###

N, K, L = map(int, input().split())
pq = [map(int, input().split()) for _ in range(K)]
rs = [map(int, input().split()) for _ in range(L)]

class UnionFind:
    def __init__(self, N):
        self.par = [n for n in range(N+1)]

    def root(self, x):
        if self.par[x] == x:
            return x
        r = self.root(self.par[x])
        self.par[x] = r
        return r

    def union(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry:
            self.par[rx] = ry

    def is_same(self, x, y):
        return self.root(x) == self.root(y)

uf_road = UnionFind(N)
uf_train = UnionFind(N)

for p, q in pq:
    uf_road.union(p, q)
for r, s in rs:
    uf_train.union(r, s)

from collections import Counter
c = Counter()
for i in range(1, N+1):
    k = (uf_road.root(i), uf_train.root(i))
    c[k] += 1

ret = []
for i in range(1, N+1):
    k = (uf_road.root(i), uf_train.root(i))
    ret.append(c[k])

print(" ".join(str(v) for v in ret))


### FIXED CODE ###

N, K, L = map(int, input().split())
pq = [map(int, input().split()) for _ in range(K)]
rs = [map(int, input().split()) for _ in range(L)]

class UnionFind:
    def __init__(self, N):
        self.par = [None] * (N+1)
        self.rank = [None] * (N+1)
        for n in range(N+1):
            self.par[n] = n
            self.rank[n] = 1

    def root(self, x):
        if self.par[x] == x:
            return x
        r = self.root(self.par[x])
        self.par[x] = r
        return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry:
            if self.rank[rx] > self.rank[ry]:
                self.par[ry] = rx
            else:
                self.par[rx] = ry
                if self.rank[rx] == self.rank[ry]:
                    self.rank[ry] += 1

    def is_same(self, x, y):
        return self.root(x) == self.root(y)

uf_road = UnionFind(N)
uf_train = UnionFind(N)

for p, q in pq:
    uf_road.unite(p, q)
for r, s in rs:
    uf_train.unite(r, s)

from collections import Counter
c = Counter()
for i in range(1, N+1):
    k = (uf_road.root(i), uf_train.root(i))
    c[k] += 1

ret = []
for i in range(1, N+1):
    k = (uf_road.root(i), uf_train.root(i))
    ret.append(c[k])

print(" ".join(str(v) for v in ret))
### BUGGY CODE ###

import sys

N,Y = map(int,input().split())

for i in range(N+1):
    for j in range(N+1):
        for k in range(N+1):
            if N == i + j + k:
                if Y == i * 10000 + j * 5000 + k * 1000:
                    print(i,j,k)
                    sys.exit()
print("-1 -1 -1")


### FIXED CODE ###

import sys

N,Y = map(int,input().split())

for i in range(N+1):
    for j in range(N+1):
        k = N - i - j

        if k >= 0 and Y == i * 10000 + j * 5000 + k * 1000:
            print(i,j,k)
            sys.exit()
print("-1 -1 -1")
### BUGGY CODE ###

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

dp = [[0]*10 for _ in range(10)]

count = 0
result = []
for i in range(n-2):
    if dp[int(s[i])] != [1]*10:
        for j in range(i+1,n-1):
            if dp[int(s[i])][int(s[j])]==0:
                count += 1
                tem = "".join(set(s[j+1:]))
                for k in range(len(tem)):
                    result.append(s[i]+s[j]+tem[k])
                dp[int(s[i])][int(s[j])]=1

ans = set(result)
print(len(ans))

### FIXED CODE ###

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

dp = [[0]*10 for _ in range(10)]

count = [0]*10

result = []

for i in range(n-2):
    if count[int(s[i])]==0:
        for j in range(i+1,n-1):
            if dp[int(s[i])][int(s[j])]==0:
                tem = "".join(set(s[j+1:]))
                for k in range(len(tem)):
                    result.append(s[i]+s[j]+tem[k])
                dp[int(s[i])][int(s[j])]=1
        count[int(s[i])]=1

ans = set(result)
print(len(ans))
### BUGGY CODE ###

n = int(input())
l = []
for _ in range(n):
    ss = input().split()
    order, string = ss[0], ss[1]
    if order == "insert":
        l.append(string)
    else:
        print('yes' if string in l else 'no')

### FIXED CODE ###

n = int(input())
l = {}
for _ in range(n):
    ss = input().split()
    order, string = ss[0], ss[1]
    if order == "insert":
        l[string] = 1
    else:
        print('yes' if string in l else 'no')
### BUGGY CODE ###

n, m = map(int, input().split())
ab = sorted([list(map(int, input().split())) for _ in range(n)])
reward = 0
for i in reversed(range(m)):
    mx = 0
    flag = 0
    for j in range(n):
        if ab[j][0] > m-i: break
        if ab[j][1] > ab[mx][1] or not flag:
            mx = j
            flag = 1
    if ab[mx][1] > 0 and flag:
        reward += ab[mx][1]
        ab[mx][1] = 0
print(reward)

### FIXED CODE ###

n, m = map(int, input().split())
jobs = [[] for _ in range(m+1)]
for i in range(n):
    a, b = map(int, input().split())
    if a > m: continue
    jobs[m-a].append(-b)
import heapq
q = []
heapq.heapify(q)
ans = 0
for i in reversed(range(m)):
    [heapq.heappush(q, job) for job in jobs[i]]
    if q: ans -= heapq.heappop(q)
print(ans)
### BUGGY CODE ###

import collections

def check(A,num):
    count = 0
    for j in A:
        n = A[j]
        if n > 1:
            if j == num:
                n -= 1
#             print("{} {}".format(j,n))

            count += n * (n - 1) / 2
    return int(count)

N = int(input())
A = list(map(int, input().split(" ")))
A2 = collections.Counter(A)
# print(A2)
for i in range(0,N):
    num = A[i]
    out = check(A2,num)
    print(out)

### FIXED CODE ###

import collections

def check(A):
    count = 0
    for j in A:
        n = A[j]
        if n > 1:
            count += n * (n - 1) / 2
            
    return int(count)


N = int(input())
A = list(map(int, input().split(" ")))
A2 = collections.Counter(A)
# print(A2)
Nsum = check(A2)
# print(Nsum)
for i in range(0,N):
    num = A[i]
    count = A2[num]
    out = Nsum - ( count - 1 )
    print(out)
### BUGGY CODE ###

from math import log2,ceil
from collections import defaultdict
import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
cnt=defaultdict(lambda :0)

for i in range(n):
    temp=a[i]
    if temp==0:continue
    digit=log2(temp)
    for j in range(ceil(digit)+1):
        if (temp>>j)&1:
            cnt[j]+=1

#print(cnt)
ans=0
for digit,count in cnt.items():
    ans=(ans+pow(2,digit)*count*(n-count))%mod
print(ans%mod)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
a=tuple(map(int,input().split()))
mod=10**9+7
cnt=[0]*60

for temp in a:
    if temp==0:continue
    digit=len(bin(temp))-2
    for j in range(digit):
        if (temp>>j)&1:
            cnt[j]=cnt[j]+1

#print(cnt)
ans=0
for i in range(60):
    if cnt[i]==0:continue
    ans=(ans+pow(2,i)*cnt[i]*(n-cnt[i]))%mod
print(ans%mod)
### BUGGY CODE ###

X = int(input())

max_v = 1

for i in range(2, X+1):
    for j in range(2, X+1):
        if i ** j <= X:
            max_v = max(max_v, i ** j)
print(max_v)



### FIXED CODE ###

X = int(input())

max_v = 1

for i in range(2, X+1):
    for j in range(2, X+1):
        if i ** j <= X:
            max_v = max(max_v, i ** j)
        else:
            break
print(max_v)
### BUGGY CODE ###

import math
import sys 
input = sys.stdin.readline
N = int(input())
x = list(map(int,input().split()))

d = [0]*(N-1)
for i in range(N-1):
    d[i] = x[i+1]-x[i]
    d[i] %= 10**9+7


kaijou = 1
for i in range(1,N):
    kaijou *= i%(10**9+7)

kaijou = math.factorial(N-1)%(10**9+7)
ans=0
x=0
k=10**9+5

def pow_r(x, n):
    """
    O(log n)
    """
    x %= (k+2)
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r(x ** 2, n // 2)%(k+2)
    else:  # standard case ② n is odd
        return (x * pow_r(x ** 2, (n - 1) // 2))%(k+2)

for i in range(N-1):
    #(i+1)**(10**9+5)を計算してyへ
    y = pow_r(i+1,k) 
    #x+= kaijou//(i+1))%(10**9+7)
    x += (kaijou*y)%(10**9+7)
    ans+= d[i]*x

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


### FIXED CODE ###

import math
import sys 
input = sys.stdin.readline

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

d = [0]*(N-1)

for i in range(N-1):
    d[i] = x[i+1]-x[i]
    d[i] %= mod


kaijou = 1
for i in range(1,N):
    kaijou *= i
    kaijou %= mod


ans=0
x=0

def pow_r(x, n):
    """
    O(log n)
    """
    x %= mod
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r(x ** 2, n // 2)%mod
    else:  # standard case ② n is odd
        return (x * (pow_r(x ** 2, (n - 1) // 2)))%mod

for i in range(N-1):
    #(i+1)%(mod-2)を計算してyへ
    y = pow_r(i+1,mod-2)
    #x+= kaijou//(i+1))%(10**9+7)
    x += kaijou*y
    ans += d[i]*x
    ans %= mod

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

import fractions
from copy import copy
from functools import reduce

n = int(input())
a = list(map(int,input().split()))
max_ = 0
def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

for i in range(n) :
    b = copy(a)
    b.pop(i)
    c = gcd_list(b)
    if max_ <= c:
        max_ = c

print(max_)


### FIXED CODE ###

from fractions import gcd
n = int(input())
a = list(map(int,input().split()))

from fractions import gcd
r = []
l = []
r.append(a[-1])

l.append(a[0])

for i in range(1,n):
    l.append(gcd(l[i-1],a[i]))
    r.append(gcd(r[i-1],a[(n-1)-i]))

l.insert(0,a[-1])
r.insert(0,a[0])


def solve(num):
    ans = gcd(l[num],r[n-1-num])
    return ans

can = []
for i in range(n):
    can.append(solve(i))

print(max(can))
### BUGGY CODE ###

N = int(input())
X = input()

d = {}
def popcount(s):
    if not s in d:
        d[s] = s.count('1')
    return d[s]

one = popcount(X)
K = int(X, 2)
T = 2**(N-1)
for i in range(N):
    pop = one
    k = K
    if X[i] == '1':
        pop -= 1
        k -= T
    else:
        pop += 1
        k += T

    ans = 0
    while k > 0:
        k %= pop
        pop = popcount(bin(k)[2:])
        ans += 1
    print(ans)
    T //= 2


### FIXED CODE ###

N = int(input())
X = input()
memo = [-1] * (N+1)
memo[0] = 0

def popcount(k):
    return bin(k).count('1')

def calc(k):
    pop = popcount(k)
    #print('  ', k, pop)
    key = k
    if memo[key] < 0:
        k %= pop
        if k == 0:
            memo[key] = 1
        else:
            memo[key] = calc(k) + 1
    return memo[key]

K = int(X, 2)
one = popcount(K)
if one == 0:
    K_MOD = K
elif one == 1:
    K_MOD   = 0
    K_MOD_M = K
else:
    K_MOD   = K % one
    K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)

T_M = [1]*(N+1)
T_P = [1]*(N+1)
for i in range(1,N+1):
    if one > 1:
        T_M[i] = (T_M[i-1]*2) % (one-1)
    T_P[i] = (T_P[i-1]*2) % (one+1)

for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T_M[N-i-1]
    else:
        pop = one + 1
        k = K_MOD_P + T_P[N-i-1]

    if pop == 0:
        print(0)
    else:
        k %= pop
        print(calc(k)+1)
### BUGGY CODE ###

N,Y=[int(s) for s in input().split()]
##N枚でY円
flag=0
i10=0
while i10*10000<=Y and i10<=N:
  i5=0
  while i10*10000+i5*5000<=Y and i10+i5<=N :
    i1=(Y%5000)//1000
    while i10*10000+i5*5000+i1*1000<=Y and i10+i5+i1<=N :
      if i10*10000+i5*5000+i1*1000==Y and i10+i5+i1==N:
        print(*[i10,i5,i1])
        flag=1
        break
      i1+=5
    if flag==1 : break
    i5+=1
  if flag==1 : break
  i10+=1
else:
  print(*[-1,-1,-1])


### FIXED CODE ###

N,Y=[int(s) for s in input().split()]
##N枚でY円
flag=0
i10=0
while i10*10000<=Y and i10<=N:
  i5=0
  while i10*10000+i5*5000<=Y and i10+i5<=N :
    i1=N-i10-i5
    if i10*10000+i5*5000+i1*1000==Y:
      print(*[i10,i5,i1])
      flag=1
      break
    i5+=1
  if flag==1 : break
  i10+=1
else:
  print(*[-1,-1,-1])
### BUGGY CODE ###

from fractions import *
n,*a=map(int,open(0).read().split())
mod=10**9+7
b=a[0]
for i in a:
    b=b*i//gcd(b,i)
ans=0
for i in a:
    ans+=b//i
    ans%=mod
print(ans)    

### FIXED CODE ###

from fractions import *
n,*a=map(int,open(0).read().split())
b=1
for i in a:b*=i//gcd(b,i)
print(sum(b//i for i in a)%(10**9+7))
### BUGGY CODE ###

MAX = 1000000007

m, n = [int(x) for x in input().split(' ')]
bi_n = bin(n)

ans = 1
dig = m
for i in range(len(bi_n)-1, 1, -1):
    if bi_n[i] == '1':
        ans *= dig
    dig *= dig
    if ans >= MAX:
        ans %= MAX

print(ans)


### FIXED CODE ###

MAX = 1000000007

m, n = [int(x) for x in input().split(' ')]
bi_n = bin(n)

ans = 1
dig = m
for i in range(len(bi_n)-1, 1, -1):
    if bi_n[i] == '1': ans *= dig
    if ans >= MAX: ans %= MAX
    dig *= dig
    if dig >= MAX: dig %= MAX

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

import numpy as np
N= int(input())
a = list(map(int, input().split(' ')))
a = np.array(a)
ret = []
for i in range(N):
    ind = np.ones(N, dtype=bool)
    ind[i] = False
    tmp = a[ind]
    print(int(np.median(tmp)))

### FIXED CODE ###

import numpy as np
N= int(input())
a = list(map(int, input().split(' ')))
sort_a = sorted(a)
small = sort_a[N//2-1]
big = sort_a[N//2]
for aa in a:
    if aa < big:
        print(big)
    else:
        print(small)
### BUGGY CODE ###

#今更だけど、Ai,Biでのバトルを行わせて、負けた方をリストに追加し、setを取って、あとから計算すればよかった
N,M=map(int,input().split())
H = [0]*N
H = list(map(int,input().split()))
A = [0]*M
B = [0]*M
for i in range(M):
  A[i],B[i]=map(int,input().split())

cnt = 0
point=[0]*N
for i in range(1,N+1):
  #iがAにもBにも無ければポイント追加
  if i not in A and i not in B:
    cnt = cnt+1

  #iがAorBにある場合には、その全ての場合にペアより大きければポイント追加
  else:
    for j in range(1,M+1):
      if i == A[j-1]:
        if H[A[j-1]-1] > H[B[j-1]-1]:
          point[i-1] = point[i-1]+1
      if i == B[j-1]:
        if H[B[j-1]-1] > H[A[j-1]-1]:
          point[i-1] = point[i-1]+1
    if point[i-1] == A.count(i)+B.count(i):
      cnt =cnt+1
print(cnt)

### FIXED CODE ###

n,m=map(int,input().split())
h=list(map(int,input().split()))
ans=[1]*n
for i in range(m):
  a,b=map(int,input().split())
  if h[a-1]<=h[b-1]:
    ans[a-1]=0
  if h[a-1]>=h[b-1]:
    ans[b-1]=0
print(ans.count(1))
### BUGGY CODE ###

N = int(input())
An = [int(n) for n in input().split()]
M = sorted(set(An))
mini=M[0]
while len(M) > 1:
    if 1 in M:
        mini=1
        break
    M = [M[0]] + [M[x]-mini for x in range(1,len(M))]
    M.sort()
    M = [x for x in M if x >= 1]
    mini = min(mini,M[0])
print(mini)    


### FIXED CODE ###

N = int(input())
An = [int(n) for n in input().split()]
M = sorted(set(An))
mini=M[0]
            
while len(M) > 1:
    M = [mini] + [x%mini for x in M[1:] if x % mini != 0]
    M.sort()
    if 1 in M:
        mini=1
        break
    mini = min(mini,M[0])
print(M[0])
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
ans = 0

for l in range(N):
  or_ = a[l]
  for r in range(l+1, N):
    if or_ & a[r] == 0:
      ans += 1
      or_ |= a[r]
    else:
      break
print(ans+N)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
ans = 0

l, r = 0, 0
xor = 0
while r < N:
  if xor ^ a[r] == xor + a[r]:
    xor = xor ^ a[r]
    ans += r-l+1
    r += 1
  else:
    xor -= a[l]
    l += 1
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
ct = 0
n = N - 1
for i in range(n):
    for j in range(i+1, N):
        x = A[i] * A[j]
        ct += x
print((ct % mod))


### FIXED CODE ###

# C　Sum of product of pairs
N = int(input())
A = list(map(int, input().split()))
t = sum(A)
x = t - A[0]
mod = 10 ** 9 + 7
ct = 0
for i in range(N-1):
    ct += A[i] * x
    x = x - A[i+1]

print((ct % mod))
int((ct % mod))
### BUGGY CODE ###

from collections import defaultdict
import sys
room_num,root_num = map(int,input().split())
#room_dis_dic = dict(zip(range(1,room_num+1),[0]+[sys.maxsize]*(room_num-1)))
connect_dic = defaultdict(list)
connected_list = [1]
next_connect_dic = {}
for _ in range(root_num):
    a,b = map(int,input().split())
    connect_dic[a].append(b)
    connect_dic[b].append(a)
    
for room_i in connected_list:
    #print(room_i)
    next_room_set = set(connect_dic[room_i])-set(connected_list)
    connected_list.extend(list(next_room_set))
    for next_room_i in next_room_set:
        next_connect_dic[next_room_i] = room_i

if len(set(range(2,room_num+1))-next_connect_dic.keys())!=0:
    print("No")
else:
    print("Yes")
    for i in range(2,room_num+1):
        print(next_connect_dic[i])

### FIXED CODE ###

from collections import defaultdict
import sys
room_num,root_num = map(int,input().split())
#room_dis_dic = dict(zip(range(1,room_num+1),[0]+[sys.maxsize]*(room_num-1)))
connect_dic = defaultdict(set)
connected_list = [1]
next_connect_dic = {}
for _ in range(root_num):
    a,b = map(int,input().split())
    connect_dic[a].add(b)
    connect_dic[b].add(a)
    
for room_i in connected_list:
    #print(room_i)
    next_room_set = {connect_to for connect_to in connect_dic[room_i] if connect_to not in next_connect_dic.keys()}
    connected_list.extend(list(next_room_set))
    for next_room_i in next_room_set:
        next_connect_dic[next_room_i] = room_i

if len(set(range(2,room_num+1))-next_connect_dic.keys())!=0:
    print("No")
else:
    print("Yes")
    for i in range(2,room_num+1):
        print(next_connect_dic[i])