Harryxun/stf_run huggingface dataset:
from collections import deque

n, m = map(int, input().split())
E = [[] for i in range(m)]

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

INF = 2 * m

dists = [INF for i in range(n)]

def bfs(cur, pre, dist):
    stack = deque([[cur, pre, dist]])
    while stack:
        cur, pre, dist = stack.popleft()
        if dist < dists[cur]:
            dists[cur] = dist
            for e in E[cur]:
                if e != pre:
                    stack.append([e, cur, dist + 1])
bfs(0, -1, 0)

print('Yes')

for i in range(1,n):
    di = dists[i]
    for e in E[i]:
        if di - 1 == dists[e]:
            print(e+1)
            break


### FIXED CODE ###

from collections import deque

n, m = map(int, input().split())
E = [[] for i in range(n)]

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

INF = 2 * m

dists = [INF for i in range(n)]

def bfs(cur, pre, dist):
    stack = deque([[cur, pre, dist]])
    while stack:
        cur, pre, dist = stack.popleft()
        if dist < dists[cur]:
            dists[cur] = dist
            for e in E[cur]:
                if e != pre:
                    stack.append([e, cur, dist + 1])
bfs(0, -1, 0)

print('Yes')

for i in range(1,n):
    di = dists[i]
    for e in E[i]:
        if di - 1 == dists[e]:
            print(e+1)
            break
N = int(input())
A = [int(input()) for _ in range(N)]

max_A = sorted(A)[-1]
second_A = sorted(A)[-2]

for n in range(N):
    if A[n] != max_A:
        print(max_A)
    else:
        print(second_A)

### FIXED CODE ###

r = int(input())
print(3 * r **2)
a, b = int(input().split())
if a*b % 2 :
    print('Odd')
else :
    print('Even')

### FIXED CODE ###

a, b = map(int, input().split())
if a*b % 2 :
    print('Odd')
else :
    print('Even')
import copy
input()
a=[int(i) for i in input().split()]
sa=copy.copy(a)
for i in range(len(a)):
    sa[i]=sa[i]-(i+1)
sa.sort()
msa=sa[int(len(sa)/2)]
sb=0
for i in range(len(a)):
    sb=sb+abs(a[i]-(msa+i+1))
print(sb)

### FIXED CODE ###

N=int(input())
if N/2==N//2:
    print(N)
else:
    print(N*2)
import sys
input = sys.stdin.readline

H, W = [int(x) for x in input().split()]
a = []
for _ in range(H):
    a.append([int(x) for x in input().split()])

place = [0, 0]
ans = []
flag = 1

for i in range(H * W - 1):
    x, y = place
    if flag:
        new_x, new_y = x, y + 1
        if new_y >= W:
            new_x, new_y = x + 1, y
            flag = 0
    else:
        new_x, new_y = x, y - 1
        if new_x < 0:
            new_x, new_y = x + 1, y
            flag = 1
    if a[x][y] % 2 == 1:
        ans.append([x + 1, y + 1, new_x + 1, new_y + 1])
        a[new_x][new_y] += 1
    place = [new_x, new_y]

print(len(ans))
for j in ans:
    print(*j)

### FIXED CODE ###

import sys
input = sys.stdin.readline

H, W = [int(x) for x in input().split()]
a = []
for _ in range(H):
    a.append([int(x) for x in input().split()])

place = [0, 0]
ans = []
flag = 1

for i in range(H * W - 1):
    x, y = place
    if flag:
        new_x, new_y = x, y + 1
        if new_y >= W:
            new_x, new_y = x + 1, y
            flag = 0
    else:
        new_x, new_y = x, y - 1
        if new_y < 0:
            new_x, new_y = x + 1, y
            flag = 1
    if a[x][y] % 2 == 1:
        ans.append([x + 1, y + 1, new_x + 1, new_y + 1])
        a[new_x][new_y] += 1
    place = [new_x, new_y]

print(len(ans))
for j in ans:
    print(*j)
from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


MOD = 1000000007
X, Y = map(int, input().split())

n = (X + Y) // 3
x = (2 * X - Y) // 3
y = (-X + 2 * Y) // 3
if (X + Y) % 3 or x < 0 or y < 0:
    print(0)
    exit()


def mod_com(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    if k > n - k:
        k = n - k
    ans = 1
    for i in range(n - k + 1, n + 1):
        ans = ans * i % MOD

    inv = [0] * (k + 1)
    inv[1] = 1
    for i in range(2, k + 1):
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        ans = ans * inv[i] % MOD

    return ans


print(mod_com(n, x))


### FIXED CODE ###

from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


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

if (X + Y) % 3:
    print(0)
    exit()

n = (X + Y) // 3
x = (2 * X - Y) // 3
y = (-X + 2 * Y) // 3
if x < 0 or y < 0:
    print(0)
    exit()

MOD = 1000000007
COM_MAX = n

fac, finv, inv = [0] * (COM_MAX + 1), [0] * (COM_MAX + 1), [0] * (COM_MAX + 1)
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1

for i in range(2, COM_MAX + 1):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD


def mod_com(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD


print(mod_com(n, x))
n = int(input())
a = [int(aa) for aa in input().split()]

def add_entry(hist, aa):
    if aa in hist:
        hist[aa] += 1
    else:
        hist[aa] = 1


def make_hist(a):
    even_hist = {}
    odd_hist = {}

    for i in range(len(a)//2):
        add_entry(even_hist, a[2*i])
        add_entry(odd_hist, a[2*i+1])

    return even_hist, odd_hist


def get_sorted_hist(hist):
    return sorted(hist.items(), key=lambda x: -x[1])

eh, oh = make_hist(a)
seh = get_sorted_hist(eh)
soh = get_sorted_hist(oh)

print(seh, soh)

if seh[0][0] != soh[0][0]:
    print(len(a) - seh[0][1] - soh[0][1])
else:
    if len(seh) == 1 and len(soh) == 1:
        print(len(a)//2)
    elif len(seh) == 1:
        print(len(a) - seh[0][1] - soh[1][1])
    elif len(soh) == 1:
        print(len(a) - soh[0][1] - seh[1][1])
    else:
        print(min(len(a) - seh[0][1] - soh[1][1], len(a) - soh[0][1] - seh[1][1]))


### FIXED CODE ###

n = input()

ans = ""
for nn in n:
    if nn == "1":
        ans += "9"
    elif nn == "9":
        ans += "1"

print(ans)
N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(len(A)-1):
  if (i+1 == A[i]):
    ans += 1
    A[i],A[i+1] = A[i+1],A[i]
if (A[-1] == l):
  ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(len(A)-1):
  if (i+1 == A[i]):
    ans += 1
    A[i],A[i+1] = A[i+1],A[i]
if (A[-1] == len(A)):
  ans += 1
print(ans)
import math


def f(b, n):
    if n < b:
        return n
    else:
        return f(b, n//b) + n % b


def main():
    n = int(input())
    s = int(input())
    if s == 1:
        print(n)
        return
    elif s == n:
        print(n+1)
        return
    elif s > n:
        print(-1)
        return
    sqrt = int(math.sqrt(n))
    for b in range(2, sqrt+1):
        if f(b, n) == s:
            print(b)
            return
    for x in range(sqrt, 0, -1):
        if s < x:
            continue
        y = s - x
        b = (n-y) // x
        if f(b, n) == s:
            print(b)
            return
    print(-1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import math


def f(b, n):
    if n < b:
        return n
    else:
        return f(b, n//b) + n % b


def main():
    n = int(input())
    s = int(input())
    if s == n:
        print(n+1)
        return
    elif s > n:
        print(-1)
        return
    sqrt = int(math.sqrt(n))
    for b in range(2, sqrt+2):
        if f(b, n) == s:
            print(b)
            return
    for x in range(sqrt, 0, -1):
        if x > s:
            continue
        y = s - x
        b = (n - y) // x
        if b >= 2 and (n - y) % x == 0 and f(b, n) == s:
            print(b)
            return
    print(-1)


if __name__ == "__main__":
    main()
n = int(input())
money = []
for _ in range(n) :
    xi, yi = input().split()
    xi = int(xi)
    if yi == "JPY" :
        xi = xi
    elif yi == "BTC" :
        xi = xi * 380000.0
    money += [xi]
print(sum(money))

### FIXED CODE ###

n = int(input())
money = []
for _ in range(n) :
    xi, yi = input().split()
    xi = float(xi)
    if yi == "JPY" :
        xi = xi
    elif yi == "BTC" :
        xi = xi * 380000.0
    money += [xi]
print(sum(money))
d, t, s = map(int, input().split())
x = d / s
if x < t:
    print('Yes')
elif x == y:
  print('Yes')
else:
    print('No')

### FIXED CODE ###

d, t, s = map(int, input().split())
if d/s <= t:
  print('Yes')
else:
  print('No')
N = int(input())
a = input().split()
for i in range(N):
    a[i] = int(a[i])

a.sort(reverse = True)
alice = 0
bob = 0
for i in range(N):
    if i % 2 == 0:
        alice += a[i]
    else:
        bob += a[i]
print(alice-bob)

### FIXED CODE ###

N = int(input())
A = int(input())

if N % 500 <= A:
    print('Yes')
else:
    print('No')
f = open("C:/Users/naoki/Desktop/Atcoder/input.txt")

H, W, M = map(int, f.readline().split())
hws = [list(map(lambda x :int(x)-1, f.readline().split())) for _ in range(M)]

booms = [set() for _ in range(H)]

yoko = [0 for _ in range(W)]
tate = [0 for _ in range(H)]

for hw in hws:
    tate[hw[0]] += 1
    yoko[hw[1]] += 1
    booms[hw[0]].add(hw[1])
    
max_tate = max(tate)
max_yoko = max(yoko)


tate_candidates = []
yoko_candidates = []

for i in range(H):
    if tate[i] == max_tate:
        tate_candidates.append(i)
        
for i in range(W):
    if yoko[i] == max_yoko:
        yoko_candidates.append(i)

exist = 0
for tate_candidate in tate_candidates:
    for yoko_candidate in yoko_candidates:
        if yoko_candidate not in booms[tate_candidate]:
            exist = 1

print(max_tate + max_yoko + (exist-1))

### FIXED CODE ###

H, W, M = map(int, input().split())
hws = [list(map(lambda x :int(x)-1, input().split())) for _ in range(M)]

booms = [set() for _ in range(H)]

yoko = [0 for _ in range(W)]
tate = [0 for _ in range(H)]

for hw in hws:
    tate[hw[0]] += 1
    yoko[hw[1]] += 1
    booms[hw[0]].add(hw[1])
    
max_tate = max(tate)
max_yoko = max(yoko)


tate_candidates = []
yoko_candidates = []

for i in range(H):
    if tate[i] == max_tate:
        tate_candidates.append(i)
        
for i in range(W):
    if yoko[i] == max_yoko:
        yoko_candidates.append(i)

exist = 0
for tate_candidate in tate_candidates:
    for yoko_candidate in yoko_candidates:
        if yoko_candidate not in booms[tate_candidate]:
            exist = 1
            break
    else:
        continue
    break
print(max_tate + max_yoko + (exist-1))
s=eval(input().replace(" ", "*").replace(".",""))
print(s//100)

### FIXED CODE ###

a,b=input().split()
a=int(a)
b=int(b.replace(".",""))
print((a*b)//100)
l = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

k = int(input())

k = k + 1

print(l[k])

### FIXED CODE ###

l = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

k = int(input())

k = k - 1

print(l[k])
import math
import itertools
n = int(input())

dic = {}
for i in range(n):
    string = input()
    sortStr = "".join(sorted(string))
    if sortStr in dic:
        dic[sortStr] += 1
    else:
        dic[sortStr] = 1

sum = 0
for num in dic.values():
    if num == 1:
        sum += 0
    else:
        sum += math.factorial(num) / 2
print(math.floor(sum))

### FIXED CODE ###

import math
n = int(input())

dic = {}


def twoKimuawaseSum(num):
    result = 0
    for i in range(1, num):
        result += i
    return result


for i in range(n):
    string = input()
    sortStr = "".join(sorted(string))
    if sortStr in dic:
        dic[sortStr] += 1
    else:
        dic[sortStr] = 1
sum = 0
for num in dic.values():
    if num == 1:
        sum += 0
    else:
        sum += twoKimuawaseSum(num)
print(math.floor(sum))
import math

a = int(input())
b = int(input())
h = int(input())
m = int(input())
ans = 0

m_r = m/5
# print(m_r)
h_r = h + m/60
# print(h_r)
# print((h_r - m_r)/12*360)
reg = (h_r - m_r)/12*360
ans = math.sqrt(a**2 + b**2 -2*a*b*math.cos(math.radians(reg)))

print(ans)

### FIXED CODE ###

import math
a,b,h,m = map(int,input().split())

ans = 0

m_r = m/5
# print(m_r)
h_r = h + m/60
# print(h_r)
# print((h_r - m_r)/12*360)
reg = (h_r - m_r)/12*360
ans = math.sqrt(a**2 + b**2 -2*a*b*math.cos(math.radians(reg)))

print(ans)
at = input().split()
top = input().split()
at_i = 0
top_i = 0
if at =='H':
  at_i = 1

if at == 'D':
  at_i = -1

if top == 'H':
	top_i = 1

if top == 'D':
  top_i = -1

if top_i * at_i == 1:
    print("H")
else :
    print("D")


### FIXED CODE ###

at = list(input())
at_i = 0
top_i = 0
if at[0] =='H':
  at_i = 1

if at[0] == 'D':
  at_i = -1

if at[2] == 'H':
	top_i = 1

if at[2] == 'D':
  top_i = -1

if top_i * at_i == 1:
    print("H")
else :
    print("D")
import sys
if __name__ == '__main__':
    N = int(input())
    W = [str(input()) for _ in range(N)]
    for i in range(1,N):
        if W[i-1][-1] != W[i][0]:
            print('No')
            sys.exit(0)
    print('Yes')

### FIXED CODE ###

if __name__ == '__main__':
    AB = [int(n) for n in input().split()]
    if AB[0] * AB[1] % 2 == 0:
        print('No')
    else:
        print('Yes')
import collections
abc = input().strip()
c = collections.Counter(abc)
if c['a']==1 and c['b' ==1 and c['c' == 1:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

import collections
abc = input().strip()
if len(abc) != 3:
    print("No")
else:
    c = collections.Counter(abc)
    if c['a']==1 and c['b'] ==1 and c['c'] == 1:
        print("Yes")
    else:
        print("No")
A, B, C = main(int, imput().split())

if (C >= A and C <= B):
  print("Yes")
  
else:
  print("No")

### FIXED CODE ###

A, B, C = map(int, input().split())
 
if (C >= A and C <= B):
  print("Yes")
  
else:
  print("No")
n = int(input())

ans_list = [100*x+10*x+x for x in range(10)]

for v in ans_list:
    if v > n:
        ans = v
        break
        
print(ans)

### FIXED CODE ###

n = int(input())

ans_list = [100*x+10*x+x for x in range(10)]

for v in ans_list:
    if v >= n:
        ans = v
        break
        
print(ans)
import sys

n, m, l = map(int, raw_input().split())
a = []
b = []
for i in range(n):
	a.append(map(int, raw_input().split()))
for i in range(m):
	b.append(map(int, raw_input().split()))

c = [[0 for i in xrange(n)] for j in xrange(l)]

for i in xrange(n):
	for j in xrange(l):
		for k in xrange(m):
			c[i][j] += a[i][k] * b[k][j]

for i in xrange(n):
	for j in xrange(l-1):
		sys.stdout.write(str(c[i][j])+" ")
	print c[i][l-1]

### FIXED CODE ###

import sys

N, M, L = map(int, raw_input().split())
a = []
b = []
for n in range(N):
	a.append(map(int, raw_input().split()))
for m in range(M):
	b.append(map(int, raw_input().split()))

c = [[0 for l in xrange(L)] for n in xrange(N)]

for n in xrange(N):
	for l in xrange(L):
		for m in xrange(M):
			c[n][l] += a[n][m] * b[m][l]

for n in xrange(N):
	for l in xrange(L-1):
		sys.stdout.write(str(c[n][l])+" ")
	print c[n][L-1]
a = {'A':'T','T':'A','G':'C','T':'C'}
print(a[input()])


### FIXED CODE ###

a = {'A':'T','T':'A','G':'C','C':'G'}
print(a[input()])
def main():
    from sys import stdin
    input = stdin.readline

    import numpy as np
    n, m = map(int, input().split())
    abc = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[u-1].append([v-1, c]) for u, v, c in abc]
    [g[i+1].append([i, 0]) for i in range(n-1)]

    import heapq

    yen = np.full(n, np.inf)
    h = [(0, 0)]
    heapq.heapify(h)
    while h:
        d, i = heapq.heappop(h)
        if yen[i] == np.inf:
            yen[i] = d
            for x, y in g[i]:
                heapq.heappush(h, (d+y, x))
    print(int(yen[n-1]))


main()

### FIXED CODE ###

n,m,s,t=map(int,input().split())
uvab=[list(map(int,input().split())) for _ in [0]*m]
g_yen=[[] for _ in [0]*n]
[g_yen[u-1].append([v-1,a]) for u,v,a,b in uvab]
[g_yen[v-1].append([u-1,a]) for u,v,a,b in uvab]

g_snk=[[] for _ in [0]*n]
[g_snk[u-1].append([v-1,b]) for u,v,a,b in uvab]
[g_snk[v-1].append([u-1,b]) for u,v,a,b in uvab]

import heapq
def dijkstra(g,start):
    inf=10**15
    dist=[inf for _ in [0]*n]
    h=[(0,start)]
    heapq.heapify(h)
    while h:
        d,i=heapq.heappop(h)
        if dist[i]==inf:
            dist[i]=d
            for x,y in g[i]:
                heapq.heappush(h,(d+y,x))
    return dist

yen=dijkstra(g_yen,s-1)
snk=dijkstra(g_snk,t-1)

cost=[yen[i]+snk[i] for i in range(n)]
m=cost[-1]
for i in range(n-1,-1,-1):
    m=min(m,cost[i])
    cost[i]=m
    
for i in cost:
    print(10**15-i)
numbers = list(input())
y = 753
result = []
for i in range(len(numbers)-3):
    x = ''.join([int(x) for x in numbers[i:i+3]])
    d = abs(x-y)
    result.append(d)
print(min(result))

### FIXED CODE ###

numbers = list(input())
y = 753
result = []
for i in range(len(numbers)-2):
    x = int(''.join(numbers[i:i+3]))
    d = abs(x-y)
    result.append(d)
print(min(result))
l = [0] * n
r = [0] * n
for i in range(n):
    l[i],r[i] = map(int, input().split())
res = 0

for i in range(n):
  res += r[i]-l[i]+1

print(res)

### FIXED CODE ###

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

for i in range(n):
  res += r[i]-l[i]+1

print(res)
from itertools import product

x1 = int(input())
x2 = input()

R_i = [i for i, x in enumerate(x2) if x == "R"]
G_i = [i for i, x in enumerate(x2) if x == "G"]
B_i = {i for i, x in enumerate(x2) if x == "B"}

R = len(R_i)
G = len(G_i)
# B = len(B_i)

xs = map(sorted, product(R_i, G_i))

s = 0
for a in xs:
    k = a[1]*2 - a[0]  # 2j-i
    if k in B_i:
        s +=1
    i = a[0]*2 - a[1]  # 2j-k
    if i in B_i:
        s +=1
    j = (a[0] + a[1]) / 2
    if j.is_integer():
        j = int(j)
        if j in B_i:
            s +=1
print(R*G*B - s)

### FIXED CODE ###

from itertools import product

x1 = int(input())
x2 = input()

R_i = [i for i, x in enumerate(x2) if x == "R"]
G_i = [i for i, x in enumerate(x2) if x == "G"]
B_i = {i for i, x in enumerate(x2) if x == "B"}

R = len(R_i)
G = len(G_i)
B = len(B_i)

xs = map(sorted, product(R_i, G_i))

s = 0
for a in xs:
    k = a[1]*2 - a[0]  # 2j-i
    if k in B_i:
        s +=1
    i = a[0]*2 - a[1]  # 2j-k
    if i in B_i:
        s +=1
    j = (a[0] + a[1]) / 2
    if j.is_integer():
        j = int(j)
        if j in B_i:
            s +=1
print(R*G*B - s)
import math

a, b, x = map(int, input().split())

x2 = x/a
c = x2*2/a - b
ans=math.atan(a/(b-c))
ans = 90 - ans / math.pi * 180
if c < 0:
    c = x2*2 / b
    ans=math.atan(c/b)
    ans = 90 - ans / math.pi * 180


print(ans)

### FIXED CODE ###

import math

a, b, x = map(int, input().split())
if (x == a*a*b):
    ans = 0.0000000000
    print(ans)
else:
    x2 = x/a
    c = x2*2/a - b
    ans=math.atan(a/(b-c))
    ans = 90 - ans / math.pi * 180
    if c <= 0:
        c = x2*2 / b
        ans=math.atan(c/b)
        ans = 90 - ans / math.pi * 180
    print(ans)
a,p ＝map(int, input().split())
print((a*3 + p) // 2)

### FIXED CODE ###

a,p = map(int, input().split())
print((a*3+p)//2)
h,w,k=map(int,input().split())
c=[input() for _ in range(h)]
count=0
for H in range(h<<1):
  for W in range(W<<1):
    b=0
    for i in range(h):
      for j in range(w):
        if (H >> i) & 1 == 0 and (W >> j) & 1 == 0 and c[i][j] == "#":
          b+=1
    if b==k:
      count+=1
print(count)

### FIXED CODE ###

h,w,k=map(int,input().split())
c=[input() for _ in range(h)]
count=0
for H in range(1<<h):
  for W in range(1<<w):
    b=0
    for i in range(h):
      for j in range(w):
        if (H >> i) & 1 == 0 and (W >> j) & 1 == 0 and c[i][j] == "#":
          b+=1
    if b==k:
      count+=1
print(count)
N,M = map(int,input().split())

A = [list(map(int, input().split()))  for i in range(M)]

graph_data = [[0] * N for i in range(N)]

for i in range(M):
    if A[i][0] > A[i][1]: A[i][0], A[i][1] = A[i][1], A[i][0]
    graph_data[A[i][0]-1][A[i][1]-1] = graph_data[A[i][1]-1][A[i][0]-1] = 1
    
visited = [False] * N

def dfs(now, depth):
    if visited[now]:
        return 0
    if depth == N - 1:
        return 1
    
    visite[now] = True
    total_path = 0
    for i in range(0,N):
        if graph_data[now][i] == 1: 
            total_path +=  dfs(i, depth + 1)
    visited[now] = False
    
    return total_path

print(dfs(0,0))

### FIXED CODE ###

import itertools

N, M = map(int, input().split())
adj_matrix = [[0]* N for _ in range(N)]

for i in range(M): #隣接行列
    a, b = map(int, input().split())
    adj_matrix[a-1][b-1] = 1
    adj_matrix[b-1][a-1] = 1

cnt = 0

for each in itertools.permutations(range(N)):
    if each[0] != 0:
        break
    factor = 1
    for i in range(N-1):
        factor *= adj_matrix[each[i]][each[i+1]]
    cnt += factor

print(cnt)
S=str(input())
T=int(input())
ans=0
for i in range (3)
	if S[i]==T[i]:
    	ans=ans+a
print(ans)

### FIXED CODE ###

S=str(input())
T=str(input())
ans=0
for i in range (3):
    if S[i]==T[i]:
        ans=ans+1
print(ans)
N, P = map(int, input().split())
S = list(input())

if P != 2 and P != 5:
    count = [0] * P
    count[0] = 1
    lst = [0] * (N + 1)
    for i in range(N):
        lst[i + 1] = ((lst[i] * 10) + int(S[i])) % P
        count[lst[i + 1]] += 1

    # print (count)
    ans = 0
    for i in count:
        ans += (i * (i - 1)) // 2

    print (ans)

if P == 2:
    count = 0
    for index, s in enumerate(S):
        if int(s) % 2 == 0:
            count += (index + 1)
    print (count)
    A

if P == 5: 
    count = 0
    for index, s in enumerate(S):
        if int(s) % 5 == 0:
            count += (index + 1)
    print (count)
    A

### FIXED CODE ###

N, P = map(int, input().split())
S = list(input())

if P != 2 and P != 5:
    count = [0] * P
    ans = 0
    tmp = 0
    for i in range(N - 1, -1, -1):
        tmp += int(S[i]) * pow(10, (N - 1 - i), P)
        tmp %= P
        ans += count[tmp]
        count[tmp] += 1
    ans += count[0]

    # print (count)
    print (ans)

if P == 2:
    count = 0
    for index, s in enumerate(S):
        if int(s) % 2 == 0:
            count += (index + 1)
    print (count)

if P == 5: 
    count = 0
    for index, s in enumerate(S):
        if int(s) % 5 == 0:
            count += (index + 1)
    print (count)
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    s = input()
    t = input()
    if t in s:
        print(0)
        sys.exit()
    lent = len(t)
    lens = len(s)
    res = []
    for i1 in range(lent):
        for i2 in range(lent, i1, -1):
            end = lens - (lent - i2)
            if t[i1:i2] in s[i1:end]:
                res.append(i1 + (lent - i2))

    r = min(res)
    print(r)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    s = input()
    t = input()
    if t in s:
        print(0)
        sys.exit()
    if len(s) == 1 and len(t) == 1:
        if t != s:
            print(1)
            sys.exit()
    lens = len(s)
    lent = len(t)
    res = set()
    for i1 in range(lens - lent + 1):
        tmp1 = sum([c1 == c2 for c1, c2 in zip(t, s[i1:i1+lent])])
        res.add(lent - tmp1)
        #print(s[i1:i1+lent], res)
    if res:
        r = min(res)
        print(r)
    else:
        print(lent)

if __name__ == '__main__':
    main()
r = int(input())
if r < 1200:
  print('ABC')
else if r < 2800:
  print('ARC')
else:
  print('AGC')

### FIXED CODE ###

r = int(input())
if r < 1200:
  print('ABC')
elif r < 2800:
  print('ARC')
else:
  print('AGC')
r,g,b=input()
if (100*r+10*g+b)/4==0:
	print("YES")
else:
  print("NO")

### FIXED CODE ###

r,g,b=(int(x) for x in input().split())

num=100*r+10*g+b
if num%4==0:
    print("YES")
else:
    print("NO")