Harryxun/stf_run huggingface dataset:
import math

x = input().split(" ")
a = int(x[0])
b = int(x[1])
c = int(x[2])
d = int(x[3])

c_count = (b//c)-((a-1)//c)
d_count = (b//d)-((a-1)//d)

cd = c*d // math.gcd(c,d)
print(cd)

### FIXED CODE ###

import fractions

x = input().split(" ")
a = int(x[0])
b = int(x[1])
c = int(x[2])
d = int(x[3])

c_count = (b//c)-((a-1)//c)
d_count = (b//d)-((a-1)//d)

cd = c*d // fractions.gcd(c,d)
cd_count = (b//cd) - ((a-1)//cd)
ans = (b+1-a)-c_count-d_count+cd_count

print(ans)
x = int(input())
L = [n**k for n in range(1, x) for k in range(2, 10) if n**k<=x]
print (max(L))

### FIXED CODE ###

x = int(input())
if x == 1:
  print(x)
else:
  L = [n**k for n in range(1, x//2) for k in range(2, 10) if n**k<=x]
  print (max(L))
n = int(input())
m = int(input())

a =( (n - 1) * (m - 1))

print(a)

### FIXED CODE ###

n, m = map(int, input().split())
print((n-1)*(m-1))
import sys
input = sys.stdin.readline
def gdc(a, b):
    if b == 0:
        return a
    return gdc(b, a%b)
def lcm(a,b):
    return a*b//gdc(a,b)

def main():
    N = int(input())
    T = [int(input()) for i in range(N)]
    ans = lcm(max(T[0], T[1]), min(T[0], T[1]))
    if N == 2:
        print(ans)
        return
    for i in range(2,N):
        ans = lcm(max(ans, T[i]), min(ans, T[i]))
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9) 
input = sys.stdin.readline
def gdc(a, b):
    if b == 0:
        return a
    return gdc(b, a%b)
def lcm(a,b):
    return a*b//gdc(a,b)

def main():
    N = int(input())
    T = [int(input()) for i in range(N)]
    if N == 1:
        return print(T[0])
    ans = lcm(max(T[0], T[1]), min(T[0], T[1]))
    if N == 2:
        print(ans)
        return
    for i in range(2,N):
        ans = lcm(max(ans, T[i]), min(ans, T[i]))
    print(ans)

if __name__ == '__main__':
    main()
A, B, C, D, E, F = map(int, input().split())
ans = []
water = []
for i in range(31):
    for j in range(31):
        tmp = 100*i*A + 100*j*B
        if tmp <= F:
            water.append(tmp)
water = list(set(water))
water.remove(0)

sugar = []
for i in range(101):
    for j in range(101):
        tmp = i*C + j*D
        if tmp <= F:
            sugar.append(tmp)
sugar = list(set(sugar))
sugar.remove(0)

            
for miz in water:
    for sato in sugar:
        if miz + sato <= F and (100 * sato) // (miz + sato) <= (100 * E) // (100 + E):
            ans.append([miz, sato, (miz * sato) // (miz + sato)])
            
ans.sort(key=lambda x:x[2], reverse = True)
print(ans[0][0]+ans[0][1], ans[0][1])

### FIXED CODE ###

A, B, C, D, E, F = map(int, input().split())
ans = []
water = []
for i in range(31):
    for j in range(31):
        tmp = 100*i*A + 100*j*B
        if tmp <= F:
            water.append(tmp)
water = list(set(water))
water.remove(0)

sugar = []
for i in range(101):
    for j in range(101):
        tmp = i*C + j*D
        if tmp <= F:
            sugar.append(tmp)
sugar = list(set(sugar))
sugar.remove(0)

            
for miz in water:
    for sato in sugar:
        if miz + sato <= F and sato / (miz + sato) <= E / (100 + E):
            ans.append([miz, sato, sato / (miz + sato)])
            
if ans:
    ans.sort(key=lambda x:x[2], reverse = True)
    print(ans[0][0]+ans[0][1], ans[0][1])
else:
    print(water[0], 0)
improt bisect
A, B, Q = map(int, input().split())
ss = [int(input()) for i in range(A)]
ts = [int(input()) for i in range(B)]
xs = [int(input()) for i in range(Q)]
INF = 10**11

-INF, INF = -1, 10**10 + 1
ss = [-INF] + ss + [INF]
ts = [-INF] + ts + [INF]

# s_e is index the nearest s on the east side of x
for x in xs:
  s_e_ix = bisect.bisect_left(ss, x)
  s_e = ss[s_e_ix]
  s_w = ss[s_e_ix - 1]
  t_e_ix = bisect.bisect_left(ts, x)
  t_e = ts[t_e_ix]
  t_w_ix = ts[t_e_ix - 1]
  
  d = INF
  for s in [s_w, s_e]:
    for t in [t_w, t_e]:
      d0 = abs(s-x) + abs(t-s)
      d1 = abs(t-x) + abs(s-t)
      d = min(d0, d1, d)
  print(d)
  
                             

### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())
ss = [int(input()) for i in range(A)]
ts = [int(input()) for i in range(B)]
xs = [int(input()) for i in range(Q)]
INF = 10**11

ss = [-INF] + ss + [INF]
ts = [-INF] + ts + [INF]
 
# s_e is index the nearest s on the east side of x
for x in xs:
  s_e_ix = bisect.bisect_left(ss, x)
  s_e = ss[s_e_ix]
  s_w = ss[s_e_ix - 1]
  
  t_e_ix = bisect.bisect_left(ts, x)
  t_e = ts[t_e_ix]
  t_w = ts[t_e_ix - 1]
  
  d = INF
  for s in [s_w, s_e]:
    for t in [t_w, t_e]:
      d0 = abs(s-x) + abs(t-s)
      d1 = abs(t-x) + abs(s-t)
      d = min(d0, d1, d)
  print(d)
bun = input()
nub = reversed(S)
n = int(len(S) / 2)

i = hug = 0
while i < n:
    if bun[i] != nub[i]:
        hug += 1
    i += 1
print(hug)

### FIXED CODE ###

S = input()
RS = reversed(S)
n = int(len(S) / 2)

ans = 0
for c1, c2 in zip(S[:n], RS):
    if c1 != c2:
        ans += 1
print(ans)
n,d=map(int,input().split())
ctr=0
for i in range(n):
  x,y=map(int,input().split())
  if (x**2+y**2)**(1/2)==d:
    ctr+=1
print(ctr)

### FIXED CODE ###

x=int(input())
if x>=30:
  print("Yes")
else:
  print("No")
# D - .. (Double Dots)

from collections import deque
N, M = map(int, input().split())
tree = [[] for _ in range(M)]
for i in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    tree[A].append(B)
    tree[B].append(A)

ans_arr = [-1] * (N)
q = deque()
ans_arr[0] = 0 
q.append(0)

while len(q)>0:
    n = q.popleft()
    for i in tree[n]:
        if ans_arr[i] == -1:
            ans_arr[i] = n+1
            q.append(i)

ans = 'Yes'
for i in ans_arr[1:]:
    if i == -1:
        ans = 'No'
        break

if ans == 'No':
    print(ans)
else:
    print(ans)
    for i in ans_arr[1:]:
        print(i)


### FIXED CODE ###

# D - .. (Double Dots)

from collections import deque

N, M = map(int, input().split())
tree = [[] for _ in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    tree[A].append(B)
    tree[B].append(A)

ans_arr = [-1] * (N)
q = deque()
ans_arr[0] = 0 
q.append(0)

while len(q)>0:
    n = q.popleft()
    for i in tree[n]:
        if ans_arr[i] == -1:
            ans_arr[i] = n+1
            q.append(i)

ans = 'Yes'
for i in ans_arr[1:]:
    if i == -1:
        ans = 'No'
        break

if ans == 'No':
    print(ans)
else:
    print(ans)
    for i in ans_arr[1:]:
        print(i)
w, h , x ,y ,r = map(int,input().split())

xLongLeft = x-r
xLongRight = x + r

yLongTop = y + r
yLongBot = y - r

if((xLongLeft >= 0 and yLongBot >= 0) and (xLongRight <= w and yLongTop <= h)):
   print('Yes')
else:
   print('No')


### FIXED CODE ###

w, h , x ,y ,r = map(int,input().split())

xLongLeft = x-r
xLongRight = x + r

yLongTop = y + r
yLongBot = y - r

if((xLongLeft >= 0 and yLongBot >= 0) and (xLongRight <= w and yLongTop <= h)):
   print('Yes')
else:
   print('No')
a,b = map(int,input().spilit())

if a > b :
    op = ">"
elif a < b:
    op = "<"
else:
    op = "=="
print("a %s b"%op)


### FIXED CODE ###

a, b = map(int, input().split())
if a < b:
    print("a < b")
elif a > b:
    print("a > b")
else:
    print("a == b")
def f(x):
    l = len(x)
    i = 0
    while x[i] == x[l-i-1]:
        i += 1
        if i > (l//2):
            return True
            break
    return False

A, B = map(int, input().split())
count = 0
for i in range(A, B+1):
    if f(i):
        count += 1
print(count)


### FIXED CODE ###

def f(x):
    l = len(x)
    i = 0
    while x[i] == x[l-i-1]:
        i += 1
        if i > (l//2):
            return True
            break
    return False

A, B = map(int, input().split())
count = 0
for i in range(A, B+1):
    if f(str(i)):
        count += 1
print(count)
H, N = map(int, input().split())
magic = list()
for _ in range(N):
    magic.append(list(map(int, input().split())))
 
magic_min = [0 for _ in range(H+1)]
for i in range(H+1):
    if i != 0 and magic_min[i] == 0:
        continue
    for A, B in magic:
        Index = i + A
        value = magic_min[i] + B
        try:
            if magic_min[Index] == 0:
                magic_min[Index] = value
            elif value < magic_min[Index]:
                magic_min[Index] = value
        
        except:
            if magic_min[-1] == 0:
                magic_min[-1] = value
            elif value < magic_min[-1]:
                magic_min[-1] = value
                
print(magic_min[-1])

### FIXED CODE ###

H,A = map(int,input().split())
if H%A == 0:
    count = H//A
else:
    count = H//A + 1
print(count)
s = input()
k = int(input())

if s[:k] in '1' * k:
    print('1')
else:
    ans = s.replace('1', '')[0]
    print(ans)


### FIXED CODE ###

s = input()
k = int(input())

if sum(map(int, list(s[:k]))) == len(s[:k]):
    print('1')
else:
    ans = s.replace('1', '')[0]
    print(ans)
s = list(input())
t = list(input())

s.sort()
s=''.join(s)

s.sort()
t.reverse()
t=''.join(t)

print(s)
print(t)

if s < t:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

import math
a,b = map(int, input().split())
x = (a + b) / 2
print(math.ceil(x))
from collections import deque
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())


N,K=LI()
mp = {}
for i in range(N-1):
    a,b = LI()
    if not a in mp: mp[a] = []
    if not b in mp: mp[b] = []
    mp[a].append(b)
    mp[b].append(a)

QU = deque([])
visited = set([1])

fact=[1]*100010
for i in range(1,100010):
    fact[i] = fact[i-1]*i%DVSR

def ncr(n,r):
    return fact[n]*INV(fact[r])*INV(fact[n-r])

pat = ncr(K, len(mp[1])+1)*fact[len(mp[1])+1]%DVSR
for i in mp[1]:
    visited.add(i)
    QU.append((i, len(mp[i])))

while QU:
    vx, cnt = QU.popleft()
    nxcnt = len(mp[vx])
    notvisited = 0
    for nx in mp[vx]:
        if not nx in visited: notvisited +=1

    for nx in mp[vx]:
        if not nx in visited:
            QU.append((nx, nxcnt))
            visited.add(nx)
    pat = pat*fact[notvisited]*ncr(K-(nxcnt+1-notvisited), notvisited)%DVSR

print(pat)


### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())


N,K=LI()
mp = {}

if N == 1:
    print(K)
    exit()

for i in range(N-1):
    a,b = LI()
    if not a in mp: mp[a] = []
    if not b in mp: mp[b] = []
    mp[a].append(b)
    mp[b].append(a)

QU = deque([])
visited = set([1])

fact=[1]*(max(N,K)+1)
for i in range(1, max(N,K)+1):
    fact[i] = fact[i-1]*i%DVSR

def ncr(n,r):
    return fact[n]*INV(fact[r])*INV(fact[n-r])%DVSR

pat = ncr(K, len(mp[1])+1)*fact[len(mp[1])+1]%DVSR
for i in mp[1]:
    visited.add(i)
    QU.append(i)

# print("initial {}".format(pat))
while QU:
    vx = QU.popleft()
    # print(vx)
    nxcnt = len(mp[vx])
    if (nxcnt+1) > K:
        print(0)
        exit()
    notvisited = 0
    for nx in mp[vx]:
        if not nx in visited:
            QU.append(nx)
            visited.add(nx)
    pat = pat*fact[nxcnt-1]*ncr(K-2, nxcnt-1)%DVSR

print(pat)
a = int(input())
b = int(input())
c = int(input())
x = int(input())
count = 0
al = range(a+1)
bl = range(b+1)
for i in al:
    for p in bl:
        if (((x-al*500-bl*100) % 50) == 0) and (0 <= (x-al*500-bl*100)):
            count += 1
        else:
            break
print(count)

### FIXED CODE ###

A = int(input())
B = int(input())
C = int(input())
X = int(input())
a = list(map(lambda x: x * 500, range(A + 1)))
b = list(map(lambda x: x * 100, range(B + 1)))
c = list(map(lambda x: x * 50, range(C + 1)))

counter = 0

for i in a:
    for p in b:
        for o in c:
            if (i + p + o) == X:
                counter += 1

print(counter)
#!/usr/bin/env python3
import sys
from bisect import bisect_right


def solve(A: int, B: int, Q: int, s: "List[int]", t: "List[int]", x: "List[int]"):
    b, d = bisect_right(s, x), bisect_right(t, x)
    INF = 10e11
    ret = INF

    for S in [s[b - 1], s[b]]:
        for T in [t[d - 1], t[d]]:
            d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
            ret = min(ret, d1, d2)
    print(ret)


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    INF = 10e11
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    s = [-INF] + [int(next(tokens)) for _ in range(A)] + [INF]  # type: "List[int]"
    t = [-INF] + [int(next(tokens)) for _ in range(B)] + [INF]  # type: "List[int]"

    for x in range(Q):
        x = int(input())
        solve(A, B, Q, s, t, x)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from datetime import datetime


def solve(S: str):
    if datetime.strptime(S, "%Y/%m/%d") <= datetime.strptime("2019/4/30", "%Y/%m/%d"):
        print("Heisei")
    else:
        print("TBD")


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)


if __name__ == "__main__":
    main()
H, W, M = map(int, input().split())
h = [0] * (H+1)
w = [0] * (W+1)
l = [[0]*W for i in range(H)]
for i in range(M):
  x, y = map(int, input().split())
  h[x] += 1
  w[y] += 1
  l[x-1][y-1] = 1

a = [i for i, x in enumerate(h) if x == max(h)]
b = [i for i, x in enumerate(w) if x == max(w)]

flag = False
for s in a:
  for t in b:
    if l[s-1][t-1] == 0:
      flag = True
      break
  if flag:
    break
if flag:
  ans = max(h)+max(w)
else:
  ans = max(h)+max(w)-1
print(ans)

### FIXED CODE ###

H, W, M = map(int, input().split())
h = [0] * (H+1)
w = [0] * (W+1)
l = set()
for i in range(M):
  x, y = map(int, input().split())
  h[x] += 1
  w[y] += 1
  l.add((x, y))
  
c = max(h)
d = max(w)
a = [i for i, x in enumerate(h) if x == c]
b = [i for i, x in enumerate(w) if x == d]

flag = False
for s in a:
  for t in b:
    if (s, t) not in l:
      flag = True
      break
  if flag:
    break
ans = c+d
if not flag:
  ans -= 1
print(ans)
import sys
from math import sqrt

for line in sys.stdin:
    n = int(line.strip())
    L, pn, tmp = int(sqrt(n)), [], [i for i in range(2, n+1)]
    while tmp[0] < L+1:
        v = tmp.pop(0)
        pn.append(v)
        tmp = list(filter(lambda x: x%v!=0, tmp))
    for t in tmp: pn.append(t)
    print(len(pn))

### FIXED CODE ###

import bisect

primes = [0, 0] + [1] * 999999
for i in range(2, 1000):
    if primes[i]:
        for j in range(i*i, 1000000, i):
            primes[j] = 0

primes = [i for i, v in enumerate(primes) if v]
while True:
    try:
        n = int(input())
    except:
        break
    print(bisect.bisect(primes, n))
S = int(input())
h = S//3600
m = (S//60)-(S//3600)
a = str(h)
b = str(m)
c = str(s)
print(a:b:c)



### FIXED CODE ###

S = int(input())
h = S//3600
m = (S//60)-60*(S//3600)
s = S%60
print('{}:{}:{}'.format(h,m,s))
N, M = (int(i) for i in input().split())
DP = [False]*N
for i in range(M):
  a, b = (int(i) for i in input().split())
  for j in (a, b):
    DP[j-1] = not DP[j-1]
for i in range(N):
  if DP[i]:
    print(NO)
    break
else:
  print(YES)

### FIXED CODE ###

N, M = (int(i) for i in input().split())
DP = [False]*N
for i in range(M):
  a, b = (int(k) for k in input().split())
  for j in (a, b):
    DP[j-1] = not DP[j-1]
for i in range(N):
  if DP[i]:
    print('NO')
    break
else:
  print('YES')
def slove(a, b):

    return min(a,b)

if __name__ == "__main__":

    a, b = inpu().split()

    ans = slove(a, b)
    print(ans)


### FIXED CODE ###

def make_num(a, b):
    num = ""
    for i in range(b):
        num += str(a)
    return num

def slove(a, b):

    num1 = make_num(a, b)
    num2 = make_num(b, a)
    
    return min(num1, num2)

if __name__ == "__main__":

    a, b = [int(i) for i in input().split()]
    ans = slove(a, b)
    print(ans)
import numpy

def countInversions(A, cnt):
    if len(A) == 1:
        return cnt

    maxi = numpy.argmax(A)
    cnt += len(A) - maxi - 1
    del A[maxi]
    return countInversions(A, cnt)

if __name__ == "__main__":
    input()
    A = map(int, raw_input().split())
    print countInversions(A, 0)

### FIXED CODE ###

import sys

cnt = 0

def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = range(n1 + 1)
    R = range(n2 + 1)

    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]

    L[n1] = 1000000000
    R[n2] = 1000000000
    i = j = 0
    global cnt

    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
            cnt += n1 - i

def mergeSort(A, left, right):
    if left + 1 < right:
        mid = (left + right) / 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    S = map(int, lines[1].split())
    mergeSort(S, 0, int(lines[0]))
    print cnt
def solve():
  count = [0] * 4
  for i in range(3):
    A, B = map(int, input().split())
    count[A - 1] += 1
    count[B - 1] += 1

  time = [0] * 2
  for c in count:
    time[c - 1] += 1

  return 'YES' if time[0] == 2 and time[1] == 2 else 'NO'

print(solve())


### FIXED CODE ###

def solve():
  count = [0] * 4
  for i in range(3):
    A, B = map(int, input().split())
    count[A - 1] += 1
    count[B - 1] += 1

  time = [0] * 2
  for c in count:
    if c != 1 and c != 2: continue
    time[c - 1] += 1

  return 'YES' if time[0] == 2 and time[1] == 2 else 'NO'

print(solve())
K=int(input())
S=input()
B=0
D=0
B=len(S)
B=int(B)
D=S+'...'
if S=>K:
    print(S)
else:
    print(D)

### FIXED CODE ###

K=int(input())
S=input()
if len(S)<=K:print(S)
else:print(S[0:K]+'...')
N = int(input())
list = [int(i) for i in input().split()]
score == 0
for i in range(N):
    if list[i] != i+1:
        score += 1
if score == 0 or 2:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

a = int(input())
 
p = list(map(int, input().split()))
 
d = 0
for i in range(a):
  if not p[i] == i+1:
    d += 1
      
 
  
if d  ==0 or d ==2:
  print("YES")
  
else:
  print("NO")
N = int(input())
A=[]
B=[]
for i in range(N):
    a,b = map(int,input().split())
    c = 0
    A.append(a)
    B.append(b)
def merge_sort(arr,b):
    if len(arr) <= 1:
        return (arr,b)

    mid = len(arr) // 2
    # ここで分割を行う
    left = arr[:mid]
    right = arr[mid:]
    leftt =b[:mid]
    rightt = b[mid:]

    # 再帰的に分割を行う
    left,leftt = merge_sort(left,leftt)
    right,rightt = merge_sort(right,rightt)

    # returnが返ってきたら、結合を行い、結合したものを次に渡す
    return merge(left, right,leftt,rightt)


def merge(left, right,leftt,rightt):
    merged = []
    mergedd = []
    l_i, r_i = 0, 0

    # ソート済み配列をマージするため、それぞれ左から見ていくだけで良い
    while l_i < len(left) and r_i < len(right):
        # ここで=をつけることで安定性を保っている
        if left[l_i] <= right[r_i]:
            merged.append(left[l_i])
            mergedd.append(leftt[l_i])
            l_i += 1
        else:
            merged.append(right[r_i])
            mergedd.append(rightt[r_i])
            r_i += 1

    # 上のwhile文のどちらかがFalseになった場合終了するため、あまりをextendする
    if l_i < len(left):
        merged.extend(left[l_i:])
        mergedd.extend(leftt[l_i:])
    if r_i < len(right):
        merged.extend(right[r_i:])
        mergedd.extend(rightt[r_i:])
    return (merged,mergedd)
B,A = merge_sort(B,A)
found = True
SUM = 0
for i in range(N):
    SUM = SUM + A[i]
    if B[i] < SUM:
        found = False
if found:
    print("Yes")
else:
    print("No")
    



### FIXED CODE ###

a = input()
if a[0]!=a[1] and a[1]!=a[2] and a[2]!=a[3] :
    print("Good")
else:
    print("Bad")
def dfs(now,prev,count):
    global flag
    flag=False
    # 今いる頂点から行ける頂点を順に next に入れてループ
    count+=1
    for next in g[now]:
        if next != prev:
            if next== n-1:
                if count==2:
                    flag=True
                    break
                else:
                    break
            dfs(next, now,count)
 
n, m = map(int, input().split())
g = [[] * n for i in range(n)]
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
dfs(0,-1,0)
if flag:
    print('POSSIBBLE')
else:
    print('IMPOSSIBLE')




    





### FIXED CODE ###

import sys

sys.setrecursionlimit(10**9)

def dfs(now,prev,count):
    # 今いる頂点から行ける頂点を順に next に入れてループ
    count+=1
    for next in g[now]:
        if count<=2:
            if next != prev:
                if next== n-1:
                    if count==2:
                        print('POSSIBLE')
                        exit()
                    else:
                        break
                dfs(next,now,count)
 
n, m = map(int, input().split())
g = [[] * n for i in range(n)]
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
dfs(0,-1,0)
print('IMPOSSIBLE')
s = input()
k = int(input())

tmp = 0
for each in s:
  if each > 1:
    print(each)
    break
  tmp += 1
  if tmp == k:
    print(1)
    break

### FIXED CODE ###

s = input()
k = int(input())

tmp = 0
for each in s:
  if int(each) > 1:
    print(each)
    break
  tmp += 1
  if tmp == k:
    print(1)
    break
A,B = map(int,input().split())
if B>A:
    print(B//A +1)
elif B = 1:    
    print(0)
else:
    print(1)

### FIXED CODE ###

A,B = map(int,input().split())
if round((B-1)%(A-1)) == 0:
  print((B - 1)//(A - 1))
else:
  print((B-1)//(A-1)+1)
n=int(input())
a=int(input())
if n%500=<a:
	print('Yes')
else:
	print('No')


### FIXED CODE ###

n=int(input())
a=int(input())
if n%500 <= a:
	print('Yes')
else:
	print('No')
x = intput()
if 'A' <= x <= 'Z':
  print("A")
else:
  print("a")

### FIXED CODE ###

x = input()
if 'A' <= x <= 'Z':
  print("A")
else:
  print("a")
import math
N, P = list(map(int, input().split()))


def cal(x):
    if P % (x ** N) == 0:
        return x
    else:
        return cal(x-1)


print(cal(int(math.pow(P, 1/ N))+1))

### FIXED CODE ###

n, p = map(int, input().split())
if n == 1:
    print(p)
else:
    for i in range(1, round(p**(1/n))+1):
        if p % i**n ==0:
            res = i
    print(res)
import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))
A_set = np.unique(A)
count_sum = np.sum([np.count_nonzero(A==i)*(np.count_nonzero(A==i)-1)/2 for i in A_set])
    
for i in A:
    print(int(count_sum-(np.count_nonzero(A==i)-1)))

### FIXED CODE ###


from collections import Counter
import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))
A_set = np.unique(A)
count_dict= Counter(A)
count_sum = np.sum([count_dict[i]*(count_dict[i]-1)/2 for i in A_set])

out = [int(count_sum-count_dict[i]+1) for i in A]
for i in out:
    print(i)
import math
n = int(input())
ln = int(math.log10(n))
a = n // (10 ** ln)
b = a * 10 ** ln - 1
c = [int(x) for x in list(str(b))]

print(sum(c))

### FIXED CODE ###

import math
n = int(input())
k = int(math.log10(n))

a = n // (10 ** k)
b = n % (10 ** k)

if k == 0:
  ans = n
elif n % 10 == 9:
  ans = k * 9 + a
else:
  ans = k * 9 + a -1

print(ans)
N = input()
SN = sum(map(int, list(N)))
print('Yes' if N%SN == 0 else 'No')

### FIXED CODE ###

N = input()
SN = sum(map(int, list(N)))
print('Yes' if int(N)%SN == 0 else 'No')