Harryxun/stf_run huggingface dataset:
import itertools

N, M = map(int, input().split())
k = []
for i in range(N):
    tmp = map(int, input().split())
    k.append(tmp)

p = input().split()

onoff = [0, 1]
kouho = list(itertools.product(onoff, repeat=N))

ans = 0
for li in kouho:
    for i in range(N):
        if p[i] == 0:
            li[i].count(0) % 2 == 0
            ans += 1
        else:
            li[i].count(0) % 2 == 1
            ans += 1
print(ans)

### FIXED CODE ###

import itertools

N, M = map(int, input().split())
k = []
for i in range(M):
    tmp = [int(j) for j in input().split()]
    k.append(tmp)

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

onoff = [0, 1]
kouho = list(itertools.product(onoff, repeat=N))

ans = 0
for li in kouho:
    flag = True
    for i in range(M):
        end = k[i][0]+1
        sum = 0
        for j in range(1, end):
            sum += li[k[i][j]-1]
        if sum % 2 != p[i]:
            flag = False
            break
    if flag == True:
        ans += 1

print(ans)
def main():
  MOD = int(1e9 + 7)
  n = int(input())
  print((pow(10,n,MOD) - 2*pow(9 , n , MOD)%MOD + pow(8 , n , MOD) + MOD)%MOD)

if __namme__ == "__main__":
  main()

### FIXED CODE ###

def main():
  MOD = int(1e9 + 7)
  n = int(input())
  print((pow(10,n,MOD) - 2*pow(9 , n , MOD)%MOD + pow(8 , n , MOD) + MOD)%MOD)
 
if __name__ == "__main__":
  main()
import math as mt
n=int(input())
t=[int(input()) for _ in range(n)]

ans=t[0]
def lcm(x,y):
    return (x*y)//mt.gcd(x,y)
for i in range(1,n):
    ans=lcm(ans,t[i])
print(ans)

### FIXED CODE ###

import fractions
n=int(input())
t=[int(input()) for _ in range(n)]

ans=t[0]

def lcm(x,y):
    return (x*y)//fractions.gcd(x,y)

for i in range(1,n):
    ans=lcm(ans,t[i])
print(ans)
a = int(input())
b = input()
c = input()
d = input()
e = int(input())
k = int(input())

if e - a =< k:
	print('Yay!')
else:
	print(':(')

### FIXED CODE ###

a = int(input())
b = input()
c = input()
d = input()
e = int(input())
k = int(input())

if e - a <= k:
	print('Yay!')
else:
	print(':(')
import heapq

N = int(input())
E = [list(map(lambda x: int(x)-1,input().split())) for _ in range(N-1)]
C = sorted(list(map(lambda x: int(x)*(-1),input().split())))
m = -sum(C[1:])
heapq.heapify(C)

V = [set() for _ in range(N)]
for u,v in E:
  V[u].add(v)
  V[v].add(u)

A = [0 for _ in range(N)]
def dfs(v,s):
  A[v] = -heapq.heappop(C)
  for u in V[v]:
    if u != s:
      dfs(u,v)
dfs(0,-1)

print(m)
print(*A)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
import heapq

N = int(input())
E = [list(map(lambda x: int(x)-1,input().split())) for _ in range(N-1)]
C = sorted(list(map(lambda x: int(x)*(-1),input().split())))
m = -sum(C[1:])
heapq.heapify(C)

V = [set() for _ in range(N)]
for u,v in E:
  V[u].add(v)
  V[v].add(u)

A = [0 for _ in range(N)]
def dfs(v,s):
  A[v] = -heapq.heappop(C)
  for u in V[v]:
    if u != s:
      dfs(u,v)
dfs(0,-1)

print(m)
print(*A)
import time
import random
N = int(input())
s = str(input())
maxlen = N//2
start = time.time()
def solve(tgt):
    for i in range(N-tgt*2+1):
        if s[i:i+tgt] in s[i+tgt:]:
            return True
    return False

ng = maxlen + 1
ok = 0
if N>650:
    ok = 2
first = 1
while ng-ok > 1:
    end = time.time()
    if end-start > 1.2:
        if ok >= 2470:
            assert()
        r = random.random.randint(ok,ng-1)
        print(r)
        exit()
    tgt = (ok+ng)//2
    if first == 1:
        tgt = (ok+ng)*127//128
        first = 0
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)


### FIXED CODE ###

from collections import defaultdict as dd
N = int(input())
s = str(input())
maxlen = N//2

def solve(tgt):
    dic = dd(int)
    st = s[tgt:2*tgt]
    dic[st] += 1
    ls = [st]
    for char in s[2*tgt:]:
        st = st[1:]+char
        dic[st] += 1
        ls.append(st)
    st = s[:tgt]
    if dic[st] > 0:
        return True
    dic[ls[0]] -= 1
    for i,char in enumerate(s[tgt:N-tgt]):
        st = st[1:]+char
        if dic[st] > 0:
            return True
        dic[ls[i+1]] -= 1
    return False

ng = maxlen + 1
ok = 0
while ng-ok > 1:
    tgt = (ok+ng)//2
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin
from collections import namedtuple
Point = namedtuple('Point', 'x y')

def make_test(p1, p2):
    gradient = (p1.y - p2.y) / (p1.x - p2.x)
    y_intercept = p1.y - gradient * p1.x
    return lambda p: gradient * p.x + y_intercept > p.y

for line in stdin:
    it = (float(s) for s in line.split(','))
    A, B, C, D = (Point(next(it), next(it)) for _ in xrange(4))

    f = make_test(A, C)
    g = make_test(B, D)
    if f(B) == f(D) or g(A) == g(C):
        print('NO')
    else:
        print('YES')

### FIXED CODE ###

from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin
from collections import namedtuple
Point = namedtuple('Point', 'x y')

def make_test(p1, p2):
    if p1.x == p2.x:
        gradient = p1.x
        return lambda p: gradient > p.x
    gradient = (p1.y - p2.y) / (p1.x - p2.x)
    y_intercept = p1.y - gradient * p1.x
    return lambda p: gradient * p.x + y_intercept > p.y

for line in stdin:
    it = (float(s) for s in line.split(','))
    A, B, C, D = (Point(next(it), next(it)) for _ in xrange(4))

    f = make_test(A, C)
    g = make_test(B, D)
    if f(B) == f(D) or g(A) == g(C):
        print('NO')
    else:
        print('YES')
#初期入力
import sys
N,M = (int(x) for x in input().split())
if N==1 and M==0:
    print(0)
    sys.exit(0)
digit ={str(i):[] for i in range(1,N+1)}

for i in range(M):
    d,n =input().split()
    digit[d].append(n)

ans =""
for i,v in digit.items():
    if i =="1" and v[0] =="0" and (len(v) ==2 or len(v) ==3): #1桁目（一番左）は✖０、最小値「１」
            print(-1)
            sys.exit(0)
    elif len(v) ==2:
        if v[0] !=v[1]: #同じ桁なのに違う値は✖
            print(-1)
            sys.exit(0)
        else:
            ans +=v[0]
    elif len(v) ==3:
        if v[0] !=v[1] or v[2] !=v[1] or v[0] !=v[2]:
            print(-1)
            sys.exit(0)
        else:
            ans +=v[0]
    elif len(v) ==1:
        ans +=v[0]
    elif len(v) ==0:
        if i =="1":
            ans +="1" #1桁目（一番左）は✖０、最小値「１」
        else:
            ans +="0"

print(ans)

### FIXED CODE ###


from collections import defaultdict
N,M = (int(x) for x in input().split())
keta_num_str = [ (input().split()) for i in range(M) ]

#各桁をキー、数字を値の辞書にする
suuji = ""
num_str_dic = defaultdict(set)
kotae_dic ={ str(i):"0" for i in range(1,N +1) } #　各桁に初期値”０”を入力。一番右（１の位）は入力がなければ無し
if 1< N:
    kotae_dic["1"] = "1" # 2桁以上の時は左の桁は最低１
for i in keta_num_str:   
    num_str_dic[i[0]].add(i[1])


for i,v in num_str_dic.items():
    if 1 < len(v) : # 一つの桁に複数の値がある時はエラー
        kotae_dic ={}
        break
    
    else:
        kotae_dic[i] = list(v)[0]

# 表示
import math
if kotae_dic == {}: # 一つの桁に複数の値の時        
    print(-1)
else:
    kotae_dic_sorted = sorted(kotae_dic.items(),key=lambda x:int(x[0]))
    kotae_str = "".join( [i[1] for i in kotae_dic_sorted ] ) # 辞書の値を連結
    kotae_int =int(kotae_str)
    if kotae_int == 0 and 1< N: # "00"などはエラー、"0"はOK
        print(-1)
    elif kotae_int == 0 and N == 1:
        print("0")
    elif 10**(N-1) > kotae_int or kotae_int >= 10** N: # 桁があってない＝一番左の桁が”０”はエラー
        print(-1)
    elif kotae_dic["1"] == "0" and 1 < N: 
        kotae_dic["1"] ="1"
    elif 1000 <= kotae_int: # 答えが１０００以上はエラー
        print(-1)

    else:
        print(kotae_int)
a,b,c = map(int, input().split())

if a == b == c || a != b != c: print("No")
else: print("Yes")

### FIXED CODE ###

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

if a == b == c or a != b != c != a: print("No")
else: print("Yes")
def func(now, ans_base, num, tree):
    ans_base.append(num[now])
    addNum = num[now]
    while len(tree[now]) > 0:
        next = tree[now].pop(0)
        num[next] += num[now]
        ans_base = func(next, ans_base, num, tree)
    return ans_base


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

tree = {}
for i in range(1, N + 1):
    tree[i] = list()

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

num = [0] * (N + 1)
for i in range(Q):
    p, x = map(int, input(). split())
    num[p] += x

ans_base = list()

result = func(1, ans_base, num, tree)

print(' '.join(list(map(str, result))))




### FIXED CODE ###

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

dictionary = [[] for i in range(N + 1)]

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

num = [0] * (N + 1)

for i in range(Q):
    p, x = map(int, input().split())
    num[p] += x

for i in range(1, N + 1):
    print(num[i])
    for j in range(0, len(dictionary[i])):
        num[dictionary[i][j]] += num[i]
x = int(input())
dp = [False] * (x + 1)
for i in range(100, 106):
    dp[i] = True
for i in range(106, x + 1):
    dp[i] = any(dp[i - j] for j in range(100, 106))
print(1 if dp[x] else 0)

### FIXED CODE ###

x = int(input())
dp = [False] * max(106, x + 1)
for i in range(100, 106):
    dp[i] = True
for i in range(106, x + 1):
    dp[i] = any(dp[i - j] for j in range(100, 106))
print(1 if dp[x] else 0)
n, m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
for i in range(n):
    a[i].reverse()

ans = n
used = set()
for i in range(m):
    count = [0]*(m+1)
    for j in range(n):
        count[a[j][-1]] += 1

    ans = min(max(count), ans)
    num = count.index(max(count))
    used.add(num)
    for j in range(n):
        if a[j][-1] in num:
            a[j].pop()

print(ans)


### FIXED CODE ###

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

ans = n
used = set()
for i in range(m):
    count = [0]*(m+1)
    for j in range(n):
        count[a[j][-1]] += 1

    ans = min(max(count), ans)
    num = count.index(max(count))
    used.add(num)
    for j in range(n):
        while len(a[j]) > 0:
            if a[j][-1] in used:
                a[j].pop()
            else:
                break

print(ans)
a=int(input())
b=int(input())
c=int(input())
d=int(input())
if a+b<=d and c+d<=d:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

a,b,c,d=map(int,input().split())
if abs (a-c)<=d or (abs(a-b)<=d and abs(b-c)<=d):
    print("Yes")
else:
    print("No")
import math
import sys
sys.setrecursionlimit(10**8)
n, k = map(int, input().split())
a = list(map(int, input().split()))
def binary_search(left, right):
    if right - left <= 0.01:
        return right
    middle = (right + left) / 2
    if is_can(middle):
        return binary_search(left, middle)
    else:
        return binary_search(middle, right)
def is_can(target):
    count = 0
    for i in range(n):
        if a[i] > target:
            count += a[i] // target
    return count <= k
p = binary_search(0, 10**10)
if is_can(int(p)):
    print(int(p))
else:
    print(int(p) + 1)


### FIXED CODE ###

import math
import sys
sys.setrecursionlimit(10**8)
n, k = map(int, input().split())
a = list(map(int, input().split()))
def binary_search(left, right):
    if right - left <= 0.01:
        return right
    middle = (right + left) / 2
    if is_can(middle):
        return binary_search(left, middle)
    else:
        return binary_search(middle, right)
def is_can(target):
    count = 0
    for i in range(n):
        if a[i] > target:
            count += a[i] // target
    return count <= k
p = binary_search(0, 10**10)
if int(p) != 0 and is_can(int(p)) :
    print(int(p))
else:
    print(int(p) + 1)
import fraction

N, X = [int(n) for n in input().split()]
x = sorted([abs(int(n) - X) for n in input().split()])

if len(x) > 1:
  gcd = math.gcd(x[0], x[1])
  for i in x:
    gcd = math.gcd(gcd, i)
else:
  gcd = x[0]
print(gcd)

### FIXED CODE ###

import fractions

N, X = [int(n) for n in input().split()]
x = sorted([abs(int(n) - X) for n in input().split()])

if len(x) > 1:
  gcd = fractions.gcd(x[0], x[1])
  for i in x:
    gcd = fractions.gcd(gcd, i)
else:
  gcd = x[0]
print(gcd)
import numpy as np
import itertools

n, m, q = map(int, input().split())
a = np.zeros(q, type=int)
b = np.zeros(q, type=int)
c = np.zeros(q, type=int)
d = np.zeros(q, type=int)

for i in range(q):
    a[i], b[i], c[i], d[i] = map(int, input().split())

A = np.array(list(itertools.combinations_with_replacement(range(1, m + 1), n)))

cnt = 0

for i in range(len(A)):
    tmp = 0
    for j in range(q):
        if(A[i][b[j]-1] - A[i][a[j]-1]) == c[j]:
            tmp = tmp + d[j]
    cnt = max(cnt, tmp)
print(cnt)

### FIXED CODE ###

import itertools

n, m, q = map(int, input().split())
a = [0] * q
b = [0] * q
c = [0] * q
d = [0] * q

for i in range(q):
    a[i], b[i], c[i], d[i] = map(int, input().split())

A = list(itertools.combinations_with_replacement(range(1, m + 1), n))

cnt = 0

for i in range(len(A)):
    tmp = 0
    for j in range(q):
        if(A[i][b[j]-1] - A[i][a[j]-1]) == c[j]:
            tmp = tmp + d[j]
    cnt = max(cnt, tmp)
print(cnt)
a,b,c = map(int,input())
if a+b >= c:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

a,b,c = map(int,input().split())
if a+b >= c:
    print("Yes")
else:
    print("No")
n = int(input())
list = list(map(int, input().split()))
for i in range(len(list)):
  copy_list = list.copy()
  copy_list.pop(i)
  copy_list.sort()
  print(copy_list[int(n/2)-1])


### FIXED CODE ###

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

if x >= a and x <= a + b:
  print('YES')
else:
  print('NO')
n=int(input())
s,p=int(input().split())
li=[]
for i in range(0,n):
  li.append((i+1,s[i],p[i]))

new_li=sorted(li,key=lambda x:x[1])

new2_li=sorted(new_li,key=lambda x:x[2] reverse=True)

for j in range(0,n):
  print(new2_li[j][0])


### FIXED CODE ###

n=int(input())

li=[]

for i in range(0,n):
  s,p=input().split()
  p=int(p)
  li.append((i+1,s,p))


new_li=sorted(li,key=lambda x:x[2] , reverse=True)
new2_li=sorted(new_li,key=lambda x:x[1])


for j in range(0,n):
  print(new2_li[j][0])
s = input()
t = input()
list = []

for i in range(len(s)-len(t)):
    n=0
    for j in range(len(t)):
        if s[i] == t[j]:
            n+=1
    list.append(n)
print(len(t)-max(list))


### FIXED CODE ###

s = input()
t = input()
list = []

for i in range(len(s)-len(t)+1):
    n=0
    U = s[i:i + len(t)]
    for j in range(len(t)):
        if U[j] != t[j]:
            n+=1
    list.append(n)
print(min(list))
x = int(raw_input())
print(x ** 3)

### FIXED CODE ###

x = input()
print(x ** 3)
#AGC030 B - Powers of two
import collections
beki=[]
for i in range(1,32):
    beki.append(2**i)#bekiは２のべき乗の配列
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
cnter=collections.Counter(A)
ans=0
for i in (reversed(beki)):
    for a in A:
        if (i//2<a<i and (i-a in cnter) )or(i//2==a and cnter[a]>=2):
            ans=ans+1
            A.remove(i-a)
print((N-len(A))//2)

### FIXED CODE ###

#AGC030 B - Powers of two
import collections
import math
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
cnter=collections.Counter(A)
ans=0
for a in A:
    inv=2**(int(math.log2(a))+1)
    if cnter[a]==0:
        continue
    if inv==2*a and cnter[inv-a]<=1:
      	continue
    if cnter[inv-a]>0:
        cnter[inv-a]=cnter[inv-a]-1
        cnter[a]=cnter[a]-1
        ans=ans+1
print(ans)
n = int(input())

s = []
for i in range(n):
  s.append(sorted(input())

print(n - len(set(s)))

### FIXED CODE ###

import collections  

n = int(input())

s = []
for i in range(n):
    s.append(str(sorted(input())))

cnt = 0
for (c, m) in collections.Counter(s).items():
    cnt += m * (m - 1) // 2
    
print(cnt)
qq

### FIXED CODE ###

a, b, c, d = list(input())
en = ["+", "-"]
for x in en:
  for y in en:
    for z in en:
      s = a + x + b + y + c + z + d
      if eval(s) == 7:
        print(s + "=7")
        exit()
s = input()
k = int(input())
m = 0
n = 0
j = 0
for i in range(len(s)):
    if s.count(s[0]) == len(s):
        print(len(s) * k // 2)
        exit()
    if len(s) <= j + 1:
        if s[0] == s[-1] == s[-2]== s[-3]== s[-4]== s[-5]== s[-6] \
                and s[0] == s[1] == s[2]== s[3]== s[4]== s[5]:
            print(s[10000000000000000000000000])
        break
    if s[j] == s[j + 1]:
        if j == len(s) - 1:
            n += 1
        else:
            m += 1
        j += 1
    j += 1
print(m * k + n)


### FIXED CODE ###

s = input()
k = int(input())
m = 0
n = 0
j = 0
for i in range(len(s)):
    if s.count(s[0]) == len(s):
        print(len(s) * k // 2)
        exit()
    if len(s) <= j + 1:
        if s[0] == s[-1] == s[-2]== s[-3]== s[-4]== s[-5]== s[len(s)//3] \
                and s[0] == s[1] == s[2]== s[3]== s[4]== s[5]:
            n+=1
        break
    if s[j] == s[j + 1]:
        if j == len(s) - 1:
            n += 1
        else:
            m += 1
        j += 1
    j += 1
print(m * k + n*(k-1))
# D - AtCoder Express 2

import numpy as np
import sys

N, M, Q = map(int, input().split())
LRpq = np.array(sys.stdin.buffer.read().split(), np.int64)
L = LRpq[:2*M:2]
R = LRpq[1:2*M:2]
p = LRpq[2*M::2]
q = LRpq[2*M+1::2]
    
train = np.zeros((N+1, N+1))
np.add.at(train, (L,R), 1)

np.cumsum(train, axis = 0, out = train)
np.cumsum(train, axis = 1, out = train)
    
ans = train[q,q] - train[p-1,q] - train[q,p-1] + train[p-1,p-1]
for i in range(Q):
    print(int(ans[i]))

### FIXED CODE ###

# D - AtCoder Express 2

import numpy as np

N, M, Q = map(int, input().split())
LR = np.zeros((N+1, N+1))

for _ in range(M):
    l, r = map(int, input().split())
    LR[l,r] += 1

np.cumsum(LR, axis = 0, out = LR)
np.cumsum(LR, axis = 1, out = LR)
    
for _ in range(Q):
    p, q = map(int, input().split())
    print(int(LR[q,q] - LR[p-1,q] - LR[q,p-1] + LR[p-1,p-1]))
from sys import stdin
import math

n = int(stdin.readline().rstrip())
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]
for i in range(1,n):
    if li[i][0] >= li[i-1][0] and li[i][1] >= li[i-1][1]:
        continue
    elif li[i][0] >= li[i-1][0] and li[i][1] < li[i-1][1]:
        bai = math.ceil(li[i-1][1]/li[i][1])
        li[i][0] *= bai
        li[i][1] *= bai
    elif li[i][0] < li[i-1][0] and li[i][1] >= li[i-1][1]:
        bai = math.ceil(li[i-1][0]/li[i][0])
        li[i][0] *= bai
        li[i][1] *= bai
    else:
        bai = max(math.ceil(li[i-1][0]/li[i][0]),math.ceil(li[i-1][1]/li[i][1]))
        li[i][0] *= bai
        li[i][1] *= bai
print(sum(li[-1]))

### FIXED CODE ###

from sys import stdin

li = list(map(int,stdin.readline().rstrip().split()))

li = list(set(li))

print(len(li))
# -*- coding: utf-8 -*-
import itertools

N = int(input())

def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)  # supposing you want multiple factors repeated
            n //= d
        d += 1
    if n > 1:
       primfac.append(n)
    return primfac

def F(a,b):
    return max([len(str(a)), len(str(b))])
    
l = primes(N)
l.append(1)
ans = []
for i in range(1,len(l)//2+1):
    comb = itertools.combinations(l, i)
    comb = list(set(list(comb)))
    for comblist in comb:
        # print(tmp)
        tmp = 1
        for x in comblist:
            tmp *= x

        ans.append(F(tmp,N//tmp))

# print(ans)
print(min(ans))


### FIXED CODE ###

# -*- coding: utf-8 -*-
import itertools

N = int(input())

def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)  # supposing you want multiple factors repeated
            n //= d
        d += 1
    if n > 1:
       primfac.append(n)
    return primfac

def F(a,b):
    return max([len(str(a)), len(str(b))])
    
if N == 1:
    print(1)
    exit()
    
l = primes(N)
l.append(1)
ans = []
for i in range(1,len(l)//2+1):
    comb = itertools.combinations(l, i)
    comb = list(set(list(comb)))
    for comblist in comb:
        # print(tmp)
        tmp = 1
        for x in comblist:
            tmp *= x

        ans.append(F(tmp,N//tmp))

# print(ans)
print(min(ans))
# -*- coding: utf-8 -*-
a, b = map(int, input().split())
c　= a * b
if c % 2 == 1:
  print('Odd')
else:
  print('Even')


### FIXED CODE ###

# -*- coding: utf-8 -*-
a, b = map(int, input().split())
c = (a * b) % 2
if c == 0:
  print("Even")
else :
  print("Odd")
N,A,B=map(int,input().split())
if  A==0:
    print(0)
elif N==A+B:
    print(A)
elif N<=A:
    print(N)
else N>A+B:
    print(N-B)

### FIXED CODE ###

N,A,B=map(int,input().split())
print(N//(A+B)*A+min(N%(A+B),A))
p=[]
q=[]
n,m = map(int,input().split())
for _ in [0]*m:
  a,b = map(int,input().split())
  if a == 1:
    p += [b]
  elif b == n:
    q += [a]
p.sort()
q.sort()
i,j = 0,0
while i<m or j<m:
    if p[i]<q[j]:
      i += 1
    elif p[i]>q[j]:
      j += 1
    else:
      print("POSSIBLE")
      exit()
print("IMPOSSIBLE")

### FIXED CODE ###

p=[]
q=[]
n,m = map(int,input().split())
for _ in [0]*m:
  a,b = map(int,input().split())
  if a == 1:
    p += [b]
  elif b == n:
    q += [a]
p.sort()
q.sort()
i,j = 0,0
while i<len(p) and j<len(q):
    if p[i]<q[j]:
      i += 1
    elif p[i]>q[j]:
      j += 1
    else:
      print("POSSIBLE")
      exit()
print("IMPOSSIBLE")
M,N = list(map(int,input().split()))
A = input().split()
A.append(M)
dis = 0
for i in range(N):
    if A[i+1]-A[i] >= dis:
        dis = A[i+1]-A[i]
        
print(A[-2]-A[0]-(dis-A[1]-A[0]))

### FIXED CODE ###

M,N = list(map(int,input().split()))
A = list(map(int,input().split()))
A.append(M+A[0])
dis = 0
for i in range(N):
    if A[i+1]-A[i] >= dis:
        dis = A[i+1]-A[i]
print(M-dis)
import random


class Dice(object):
    def __init__(self):
        self.t = 1
        self.s = 2
        self.e = 3
        self.w = 4
        self.n = 5
        self.b = 6

    def __init__(self, faces):
        self.t = faces[0]
        self.s = faces[1]
        self.e = faces[2]
        self.w = faces[3]
        self.n = faces[4]
        self.b = faces[5]

    def roll(self, direct):
        if direct == 0:
            self.t, self.s, self.b, self.n = self.n, self.t, self.s, self.b
        elif direct == 1:
            self.t, self.w, self.b, self.e = self.e, self.t, self.w, self.b
        elif direct == 2:
            self.n, self.w, self.s, self.e = self.w, self.s, self.e, self.n

    def is_equal(dice):
        if self.t == dice.t and self.s == dice.s and self.e == dice.e and self.w == dice.w and self.n == dice.n and self.b == dice.b:
            return True
        else:
            return False

faces1 = list(map(int, input().split()))
dice1 = Dice(faces1)
faces2 = list(map(int, input().split()))
dice2 = Dice(faces2)

flag = False

for i in range(10000):
    dice2.roll(random.randint(0, 3))
    if dice1.is_equal(dice2):
        flag = True
        break

if flag:
    print('Yes')
else:
    print('No')



### FIXED CODE ###

import random


class Dice(object):
    def __init__(self):
        self.t = 1
        self.s = 2
        self.e = 3
        self.w = 4
        self.n = 5
        self.b = 6

    def __init__(self, faces):
        self.t = faces[0]
        self.s = faces[1]
        self.e = faces[2]
        self.w = faces[3]
        self.n = faces[4]
        self.b = faces[5]

    def roll(self, direct):
        if direct == 0:
            self.t, self.s, self.b, self.n = self.n, self.t, self.s, self.b
        elif direct == 1:
            self.t, self.w, self.b, self.e = self.e, self.t, self.w, self.b
        elif direct == 2:
            self.n, self.w, self.s, self.e = self.w, self.s, self.e, self.n

    def is_equal(self, dice):
        if self.t == dice.t and self.s == dice.s and self.e == dice.e and self.w == dice.w and self.n == dice.n and self.b == dice.b:
            return True
        else:
            return False

faces1 = list(map(int, input().split()))
dice1 = Dice(faces1)
faces2 = list(map(int, input().split()))
dice2 = Dice(faces2)

flag = False

for i in range(10000):
    dice2.roll(random.randint(0, 3))
    if dice1.is_equal(dice2):
        flag = True
        break

if flag:
    print('Yes')
else:
    print('No')