Harryxun/stf_run huggingface dataset:
from collections import deque
import sys
sys.setrecursionlimit(8000)
N, M = map(int, input().split())
graph = [[] for j in range(M)]
q = deque([])
depth_array = [-1 for i in range(N)]

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

def bfs(graph, q, depth_array):
    # 終了条件
    if len(q) == 0:
        return depth_array

    cur_room = q.popleft()

    # キューに追加
    for r in graph[cur_room]:
        if depth_array[r] == -1: #未訪問なら
            q.append(r)
            depth_array[r] = depth_array[cur_room] + 1

    return bfs(graph, q, depth_array)
    
# init
q.append(0)
depth_array[0] = 0
depth_array = bfs(graph, q, depth_array)

mark_array = [-1 for i in range(N)]
#print(depth_array)

for room, depth in enumerate(depth_array):
    for node in graph[room]:
        if depth_array[node] + 1 == depth_array[room]:
            mark_array[room] = node
if -1 in mark_array[1:]:
    print("No")
else:
    print("Yes")
    for m in mark_array[1:]:
        print(m+1)

### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(200000)
N, M = map(int, input().split())
graph = [[] for j in range(N)]
q = deque([])
depth_array = [-1 for i in range(N)]

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

def bfs(graph, q, depth_array):
    # 終了条件
    if len(q) == 0:
        return depth_array

    cur_room = q.popleft()

    # キューに追加
    for r in graph[cur_room]:
        if depth_array[r] == -1: #未訪問なら
            q.append(r)
            depth_array[r] = depth_array[cur_room] + 1

    return bfs(graph, q, depth_array)
    
# init
q.append(0)
depth_array[0] = 0
depth_array = bfs(graph, q, depth_array)

mark_array = [-1 for i in range(N)]
#print(depth_array)

for room, depth in enumerate(depth_array):
    for node in graph[room]:
        if depth_array[node] + 1 == depth_array[room]:
            mark_array[room] = node

if -1 in mark_array[1:]:
    print("No")
else:
    print("Yes")
    for m in mark_array[1:]:
        print(m+1)
n,m = map(int,input().split())
ans = [0]*n
for i in range(m):
  s,c = map(int,input().split())
  if ans[s-1] != 0 and ans[s-1] != c:
    print(-1)
    exit()
  elif n != 1 and s == 1 and c == 0:
    print(-1)
    exit()
  else:
    ans[s-1] = c
ans_f = "".join((map(str,ans)))
if n>1 and ans_f[0] == "0":
  print("1"+ans_f[1::])
else:
  print(ans_f)

### FIXED CODE ###

n = int(input())
ans = n//2
if n/2 == ans:
  print(ans)
else:
  print(ans+1)
a, b = map(int, input().split())

print(a ^ b ^ c)


### FIXED CODE ###

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

if a == b:
    print(c)
elif b == c:
    print(a)
else:
    print(b)
X, Y = map(int, input().split())
ans = 0
k = [3, 2, 1]
if X <= 3:
    ans += k[X-1]
if Y <= 3:
    ans += k[X-1]
if X == 1 and Y == 1:
    ans += 4
print(ans * 100000)

### FIXED CODE ###

X, Y = map(int, input().split())
ans = 0
k = [3, 2, 1]
if X <= 3:
    ans += k[X-1]
if Y <= 3:
    ans += k[Y-1]
if X == 1 and Y == 1:
    ans += 4
print(ans * 100000)
<?php
function pc_permute($items, $perms = array( )) {
    if (empty($items)) {
        $return = array($perms);
    } else {
        $return = array();
        for ($i =  0; $i < count($items); $i++) {
            $newitems = $items;
            $newperms = $perms;
            list($foo) = array_splice($newitems, $i, 1);
            array_unshift($newperms, $foo);
            $return = array_merge($return, pc_permute($newitems, $newperms));
        }
    }
    return $return;
}
$N = intval(trim(fgets(STDIN)));
$P = explode(" ",fgets(STDIN));
$Q = explode(" ",fgets(STDIN));

$a = range(1,$N);
$perms = pc_permute($a);
sort($perms);

$p_index = -1;
$q_index = -1;

for ($i=0; $i < count($perms); $i++){
  if ($perms[$i] == $P){
    $p_index = $i;
  }
  if ($perms[$i] == $Q){
    $q_index = $i;
  }
}

$ans = abs($p_index - $q_index);
echo $ans;


### FIXED CODE ###

import itertools

def main():
    N = int(input())
    
    P = list(map(int, input().split()))
    Q = list(map(int, input().split()))
    
    combi = list(itertools.permutations(range(1, N+1)))
    
    pi = 0
    qi = 0
    for i in range(len(combi)):
        if list(combi[i]) == P:
            pi = i + 1
        if list(combi[i]) == Q:
            qi = i + 1
            
            
    print(abs(qi - pi))
    
main()
n = int(input())
b = [int(x) for x in input().split]
b.reverse()
b_counts = len(b)

for i in range(n):
    for j in range(n):
        
        if b[j] == b_counts-b.index()+1:
            ans = b.pop(j)
            b_counts -= 1
            print(ans)
        elif b[j] > b_counb_counts-b.index()+1:
            ans = -1
            break
        
        if b_counts == 0:
            break
print(ans)

### FIXED CODE ###

n = int(input())
b = list(map(int, input().split()))
b.reverse()
ans_set = [0]*n
ans = 0

for i in range(n):
    if ans == -1:
        break
    
    for j in range(n):
        if b[j] == n-j:
            ans = b.pop(j)
            ans_set[n-1] = ans
            n -= 1
            break
            
        elif b[j] > n-j:
            ans = -1
            print(ans)
            break

        if n == 0:
            break

if ans != -1:
    for k in ans_set:
        print(k)
L=list(input())
L=list(set(L))
L=sorted(L)
R=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
for i in range(26):
  if L[i]!=R[i]:
    print(R[i])
    exit()
print("None")

### FIXED CODE ###

L=list(input())
L=list(set(L))
L=sorted(L)
R=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
for i in range(min(26,len(L))):
  if L[i]!=R[i]:
    print(R[i])
    exit()
if len(L)<26:
  print(R[len(L)])
  exit()
print("None")
import numpy as np
N, K = map(int, input().split())
 
A = np.zeros(N, dtype=int)

### FIXED CODE ###

import numpy as np

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

A = np.zeros(N, dtype=int)

for _ in range(K):
    input()
    for i in input().split():
        A[int(i) - 1] += 1

ans = 0
for i in A:
    if i == 0:
        ans += 1
print(ans)
ok = [[0,4,8], [2,4,6], [0,1,2], [3,4,5], [6,7,8], [0,3,6], [1,4,7], [2,5,8]]
while True:
    s = input()
    if len(s) == 0:
        break
    maru = []
    batu = []
    for i in range(9):
        if s[i] == 'o':
            maru.append(i)
        elif s[i] == 'x':
            batu.append(i)
    flag = False
    for i in ok:
        if i == maru:
            print("o")
            flag = True
            break
        elif i ==batu:
            print("x")
            flag = True
            break
    if flag:
        continue
    print("d")

### FIXED CODE ###

ok = [[0,4,8], [2,4,6], [0,1,2], [3,4,5], [6,7,8], [0,3,6], [1,4,7], [2,5,8]]
while True:
    try:
        s = input()
    except EOFError:
        break
    flag = False
    for i in ok:
        if s[i[0]] == s[i[1]] == s[i[2]] and s[i[0]] != 's':
            print(s[i[0]])
            flag = True
            break
    if flag:
        continue
    print("d")
s_=input()
t=input()
ans=[]
n=len(s_)
m=len(t)
ind=0
dic={}
for i in range(n-m+1):
	con1=True
	for j in range(m):
		if s_[i+j] !=t[j] and s_[i+j]!='?':
			con1=False
			dic.clear()
			break
		else:
			dic[i+j]=t[j]
	
	if con1:
		lis=list(s_)
		if len(dic)!=0:
			for key in dic:
				lis[key]=dic[key]
			lis=''.join(lis)
		lis=lis.replace('?','a')
		ans.append(lis)
		dic.clear()
if con1:
	ans.sort()
	print(ans[0])
else:
	print('UNRESTORABLE')

	


### FIXED CODE ###

s_=input()
t=input()
ans=[]
n=len(s_)
m=len(t)
ind=0
dic={}
if m > n:
	print('UNRESTORABLE')
else:
	for i in range(n-m+1):
		con1=True
		for j in range(m):
			if s_[i+j] !=t[j] and s_[i+j]!='?':
				con1=False
				dic.clear()
				break
			else:
				dic[i+j]=t[j]
	
		if con1:
			lis=list(s_)
			if len(dic)!=0:
				for key in dic:
					lis[key]=dic[key]
				lis=''.join(lis)
			lis=lis.replace('?','a')
			ans.append(lis)
			dic.clear()
	if len(ans)!=0:
		ans.sort()
		print(ans[0])
	else:
		print('UNRESTORABLE')
# リストの宣言
A = []

# 入力の最初の行に、数列の長さを表す整数 N が与えられます。
# 2 行目に、N 個の整数が空白区切りで与えられます。
LENGTH =int(input())
A = input().split()

# 変数
N = 0
M = LENGTH - 1
CHANGE = 0

# BubbleSort(A)
#  for i = 0 to A.length-1
while N <= LENGTH -1 :
    M = LENGTH - 1
    print ('N=',N)
#      for j = A.length-1 downto i+1
    while M >= N + 1:
        print  ('-M=',M)
#          if A[j] < A[j-1]
        if A[M] < A[M-1] :
            tmp = A[M-1]
            A[M-1] = A[M]
            A[M] = tmp
            CHANGE += 1
        M -= 1
    N += 1

print(" ".join(map(str,A)))
print (CHANGE)



### FIXED CODE ###

# リストの宣言
A = []

# 入力の最初の行に、数列の長さを表す整数 N が与えられます。
# 2 行目に、N 個の整数が空白区切りで与えられます。
LENGTH =int(input())
A = input().split()

# 変数
N = 0
M = LENGTH - 1
CHANGE = 0

# BubbleSort(A)
#  for i = 0 to A.length-1
while N <= LENGTH -1 :
    M = LENGTH - 1
#    print ('N=',N)
#      for j = A.length-1 downto i+1
    while M >= N + 1:
#       print  ('-M=',M)
#          if A[j] < A[j-1]
        if int(A[M]) < int(A[M-1]) :
            tmp = A[M-1]
            A[M-1] = A[M]
            A[M] = tmp
            CHANGE += 1
        M -= 1
    N += 1

print(" ".join(map(str,A)))
print (CHANGE)
N,=list(map(int, input().split()))
A = list(map(int, input().split()))
Q, = list(map(int, input().split()))
B = [0 for i in range(Q)]
C = [0 for i in range(Q)]
for q in range(Q):
  B[q],C[q]=list(map(int, input().split())) 
li=[0 for i in range(100000)]
for a in A:
  li[a]+=1
su=sum(A)
for q in range(Q):
  su = su + li[B[q]] * (C[q]-B[q])
  li[C[q]]+=li[B[q]]
  li[B[q]]=0
  print(su)  

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = [0] * Q
C = [0] * Q  
li=[0]*100001
for a in A:
  li[a]+=1
su=sum(A)
for q in range(Q):
  B,C=list(map(int, input().split())) 
  su += li[B] * (C-B)
  li[C]+=li[B]
  li[B]=0
  print(su)
N=int(input())
F=[]
for i in range(N):
    tem = list(map(int,input().split()))
    F.append(tem)
P=[]
for i in range(N):
    tem = list(map(int,input().split()))
    P.append(tem)


max_benef =-float("inf")

for d in range(1,2**10):
    op = ["-"] * 10  # あらかじめ ["-", "-", "-"] というリストを作っておく
    for j in range(10):
        if ((d >> j) & 1):
            op[10 - 1 - j] = "+"  # フラグが立っていた箇所を "+" で上書き
    
    m =0
    count=[0 for t in range(10)]
    for t in range(10):
        if op[t]=="+":
            for s in range(10):
                if F[s][t]==1:
                    count[s]+=1
        for s in range(10):
            m += P[s][count[s]]
        ans = max(m,ans)
    
    print(ans)






### FIXED CODE ###

N=int(input())
F=[]
for i in range(N):
    tem = list(map(int,input().split()))
    F.append(tem)
P=[]
for i in range(N):
    tem = list(map(int,input().split()))
    P.append(tem)


max_benef =-float("inf")

for d in range(1,2**10):
    op = ["-"] * 10  # あらかじめ ["-", "-", "-"] というリストを作っておく
    for j in range(10):
        if ((d >> j) & 1):
            op[10 - 1 - j] = "+"  # フラグが立っていた箇所を "+" で上書き
    
    m =0
    count=[0 for s in range(N)]
    for t in range(10):
        if op[t]=="+":
            for s in range(N):
                if F[s][t]==1:
                    count[s]+=1
    for s in range(N):
        m += P[s][count[s]]
    max_benef = max(m,max_benef)
    
print(max_benef)
# li = [[0] * 4 for i in range(3)]

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

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

S = input()


memo = {}


def dfs(n):
    # print(n)
    if n in memo:
        return memo[n]

    i = n + 1
    while i <= N:
        temp_int = int(S[n:i])
        # print(temp_int)
        if temp_int % P == 0:
            memo[n] = 1 + dfs(i)
            return memo[n]

        i += 1
    return 0


ans = 0
for i in range(N):
    temp = dfs(i)
    ans += temp

print(ans)


### FIXED CODE ###

N, P = map(int, input().split())
S = input()
now = 0
hyou = [0] * P
hyou[0] = 1
cnt = 1
ans = 0

if P == 2 or P == 5:
    for i, t in enumerate(S[::-1]):
        temp = int(t)
        if temp % P == 0:

            ans += N - i
    print(ans)
    exit()

for i, t in enumerate(S[::-1]):
    now = (now + int(t) * pow(10, i, P)) % P
    ans += hyou[now]
    hyou[now] += 1

print(ans)
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a_, b_ = [0], [0]

for i in range(n):
    a_.append(a_[i] + a[i])
for i in range(n):
    b_.append(b_[i] + b[i])

ans, j = 0, m - 1

for i in range(n + 1):
    if a_[i] > k:
        break
    while b_[j] > k - a_[i]:
        j -= 1
    ans = max(ans, i + j)
print(ans)

### FIXED CODE ###

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

a_, b_ = [0], [0]

for i in range(n):
    a_.append(a_[i] + a[i])
for i in range(m):
    b_.append(b_[i] + b[i])

ans, j = 0, m

for i in range(n + 1):
    if a_[i] > k:
        break
    while b_[j] > k - a_[i]:
        j -= 1
    ans = max(ans, i + j)
print(ans)
N = input()
M = input()
A = (factorial(N)*factorial(N-1))+(factorial(M)*factorial(M-1))/2
print A

### FIXED CODE ###

from math import *


N,M = list(map(int,input().split(" ")))
A = (N*(N-1))/2+(M*(M-1))/2
print (int(A))
def Fib(n, memo={}):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = Fib(n-1,memo)+Fib(n-2,memo)
        return memo[n]
n,m=map(int,input().split())
if m==0:
	print(Fib(n+1)%(10**9+7))
	exit()
a=[]
for i in range(m):
	a.append(int(input()))
if a[0]!=1:
	a.insert(0,-1)
if a[-1]!=n-1:
	a.append(n+1)
b=[]
for i in range(len(a)-1):
	b.append(a[i+1]-a[i]-1)
	if a[i+1]-a[i]==1:
		print(0)
		exit()
ans=1
for i in range(len(b)):
	ans*=Fib(b[i])
	ans%=10**9+7
print(ans)

### FIXED CODE ###

def Fib(n):
    a=[0,1,1]
    if n<=2:
    	return a[n]
    else:
    	for i in range(n-2):
    		a.append(a[i+1]+a[i+2])
    	return a[n]
n,m=map(int,input().split())
if m==0:
	print(Fib(n+1)%(10**9+7))
	exit()
a=[]
for i in range(m):
	a.append(int(input()))
if a[0]!=1:
	a.insert(0,-1)
if a[-1]!=n-1:
	a.append(n+1)
b=[]
for i in range(len(a)-1):
	b.append(a[i+1]-a[i]-1)
	if a[i+1]-a[i]==1:
		print(0)
		exit()
ans=1
for i in range(len(b)):
	ans*=Fib(b[i])
	ans%=10**9+7
print(ans)
n = int(input())
xy = sorted([tuple(map(int,input().split())) for i in range(n)])
dif = []
for i in range(n-1):
    dif.append(tuple([xy[i+1][0]-xy[i][0],xy[i+1][1]-xy[i][1]]))
from collections import Counter
c = Counter(dif)
print(n-c[list(c)[0]])

### FIXED CODE ###

n = int(input())
xy = sorted([tuple(map(int,input().split())) for i in range(n)])
if n==1:
    print(1)
    exit()
dif = []
for i in range(n):
    for j in range(i+1,n):
        dif.append(tuple([xy[j][0]-xy[i][0],xy[j][1]-xy[i][1]]))
from collections import Counter
c = Counter(dif)
print(n-max(c.values()))
import sys
import numpy as np
from collections import defaultdict
import bisect

sys.setrecursionlimit(10**6)
M = 1000000007
N = int(input())
left = list(map(int, input().split()))

indices = defaultdict(list)
for i, x in enumerate(left):
    indices[x].append(i)


def dp(t, n1, n2, n3):
    remaining = n1 + n2 + n3
    if remaining < 0:
        return 0
    cached = t[n1, n2, n3]
    if cached >= 0:
        return cached
    last_cnt = left[remaining - 1] + 1
    res = 0
    if last_cnt == n1:
        res += dp(t, n1 - 1, n2, n3)
        res %= M
    if last_cnt == n2:
        res += dp(t, n1, n2 - 1, n3)
        res %= M
    if last_cnt == n3:
        res += dp(t, n1, n2, n3 - 1)
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[n1, n2, n3] = res
    return res


def solve():
    heads = [0, 0, 0]
    for i in range(N):
        k = len(indices[i])
        if k == 3:
            heads[0] = heads[1] = heads[2] = i + 1
        elif k == 2:
            heads[0] = heads[1] = i + 1
        elif k == 1:
            heads[0] = i + 1
        else:
            break
    t = -np.ones(shape=(heads[0] + 1, heads[1] + 1, heads[2] + 1), dtype=np.int64)
    t[0, 0, 0] = 1
    num_colors = len(indices[0])
    base = dp(t, heads[0], heads[1], heads[2])
    if len(indices[0]) < 3:
        return 3 * base
    else:
        return base


print(solve())


### FIXED CODE ###

import itertools
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 9)
M = 1000000007
N = int(sys.stdin.readline())
left = list(map(int, sys.stdin.read().split()))
counter = Counter(left)


def dp(t, ns):
    cached = t.get(ns)
    if cached is not None:
        return cached
    remaining = sum(ns)
    assert remaining > 0
    last_cnt = left[remaining - 1] + 1
    n1, n2, n3 = ns
    res = 0
    if last_cnt == n1:
        res += dp(t, tuple(sorted([n1 - 1, n2, n3])))
        res %= M
    if last_cnt == n2:
        res += dp(t, tuple(sorted([n1, n2 - 1, n3])))
        res %= M
    if last_cnt == n3:
        res += dp(t, tuple(sorted([n1, n2, n3 - 1])))
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[ns] = res
    return res


def solve():
    h = [0, 0, 0]
    for i in range(N):
        k = counter[i]
        if k == 3:
            h[0] = h[1] = h[2] = i + 1
        elif k == 2:
            h[0] = h[1] = i + 1
        elif k == 1:
            h[0] = i + 1
        else:
            break
    if sum(h) != N:
        return 0
    t = dict()
    t[0, 0, 0] = 1
    res = dp(t, tuple(sorted(h)))
    return (res * len(set(itertools.permutations(h)))) % M


print(solve())
import sys

AList = []
BingoList = [[0, 0, 0],
             [0, 0, 0],
             [0, 0, 0]]

for i in range(3):
    AList.append(list(map(int, input().split())))
    

N = int(input())

tmp = -1
for i in range(N):
    tmp = int(input())
    for p in range(3):
        for q in range(3):
            if AList[p][q] == tmp:
                BingoList[i][q] = 1

for i in range(3):
    if BingoList[i][0] == 1 and BingoList[i][1] == 1 and BingoList[i][2] == 1:
        print('Yes')
        sys.exit(0)

for i in range(3):
    if BingoList[0][i] == 1 and BingoList[1][i] == 1 and BingoList[2][i] == 1:
        print('Yes')
        sys.exit(0)

if BingoList[0][0] == 1 and BingoList[1][1] == 1 and BingoList[2][2] == 1:
    print('Yes')
elif BingoList[2][0] == 1 and BingoList[1][1] == 1 and BingoList[0][2] == 1:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

import sys

AList = []
BingoList = [[0, 0, 0],
             [0, 0, 0],
             [0, 0, 0]]

for i in range(3):
    AList.append(list(map(int, input().split())))
    

N = int(input())

tmp = -1
for i in range(N):
    tmp = int(input())
    for p in range(3):
        for q in range(3):
            if AList[p][q] == tmp:
                BingoList[p][q] = 1

for i in range(3):
    if BingoList[i][0] == 1 and BingoList[i][1] == 1 and BingoList[i][2] == 1:
        print('Yes')
        sys.exit(0)

for i in range(3):
    if BingoList[0][i] == 1 and BingoList[1][i] == 1 and BingoList[2][i] == 1:
        print('Yes')
        sys.exit(0)

if BingoList[0][0] == 1 and BingoList[1][1] == 1 and BingoList[2][2] == 1:
    print('Yes')
elif BingoList[2][0] == 1 and BingoList[1][1] == 1 and BingoList[0][2] == 1:
    print('Yes')
else:
    print('No')
A=input()
print(A.index("z")-A.index("a"))

### FIXED CODE ###

A=input()
n=A.index("A")
m=A[::-1].index("Z")
print(len(A)-n-m)
N, M = map(int, input().split())
ab = [[] for _ in range(M)]

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

count = 0

def dfs(i, now, done):
    global count
    if i == N-1:
        count += 1
        return

    for j in ab[now]:
        if j not in done:
            dfs(i+1, j, done + [j])
    return

dfs(0, 0, [0])
print(count)

### FIXED CODE ###

import itertools

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

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

ans = 0

for i in itertools.permutations(range(n), n):#N!
    if i[0] == 0:
        for j in range(n):
            if j == n - 1:
                ans += 1
                break
            if not path[i[j]][i[j + 1]]:
                break

print(ans)
import numpy as np
N, M = map(int, input().split())
s, c = [], []
for i in range(M):
  tmp_s, tmp_c = map(int, input().split())
  s.append(tmp_s)
  c.append(tmp_c)

flag = 0
v_set = [999 for i in range(N)]
#print(v_set)
for i in range(M):
  if N == 1:	# 一桁のとき
    if v_set[0] == 999:
      v_set[0] = c[i]
      flag = 1
    elif v_set[0] != 999 and c[i] < v_set[0]:
      v_set[0] = c[i]
      flag = 1
  else:			# ２桁以上のとき
    if s[i] == 1 and c[i] == 0:
      flag = 0
      break
    elif v_set[s[i]-1] == 999:
      v_set[s[i]-1] = c[i]
      flag = 1
    elif v_set[s[i]-1] != 999 and c[i] < v_set[s[i]-1]:
      v_set[s[i]-1] = c[i]
      flag = 1
if flag == 0:
  print(-1)
else:
  for i in range(N):
    if v_set[i] == 999:
      v_set[i] = 0
  if v_set[i] == 0:
    print(-1)
  else:
    print(str(int(v_set[0]))+str(int(v_set[1]))+str(int(v_set[2])))
  

### FIXED CODE ###

import numpy as np
N, M = map(int, input().split())
s, c = [], []
for i in range(M):
  tmp_s, tmp_c = map(int, input().split())
  s.append(tmp_s)
  c.append(tmp_c)

v_set = [999 for i in range(N)]
if N == 1:
  if M == 0:
    print(0)
  else:
    for i in range(M):
      if v_set[0] == 999 or v_set[0] == c[i]:
        v_set[0] = c[i]
      else:
        v_set[0] = -1
        break
    print(v_set[0])
elif N >= 2:
  for i in range(M):
    if v_set[s[i]-1] == 999 or v_set[s[i]-1] == c[i]:
      v_set[s[i]-1] = c[i]
    else:
      v_set[0] = 0
      break
  if v_set[0] == 0:
    print(-1)
  else:
    if v_set[0] == 999:
      v_set[0] = 1
    for i in range(1,N):
      if v_set[i] == 999:
        v_set[i] = 0
    out = ''
    for i in range(N):
      out += str(int(v_set[i]))
    print(out)
def main():
    n,m = map(int,input().split())
    A = []
    for _ in range(m):
        a = int(input())
        A.append(a)
    mod = 10**9+7
    def root(n):
        if n==0 or n==1:
            return 1
        else:
            if n-1 in A and n-2 in A:
                return 0
            elif n-1 in A and n-2 not in A:
                return pow(root(n-2),1,mod)
            elif n-1 not in A and n-2 in A:
                return pow(root(n-1),1,mod)
            else:
                return pow(root(n-1)+root(n-2),1,mod)
    print(root(n))

if __name__ == "__main__":
    main()

### FIXED CODE ###

from functools import lru_cache

def main():
    n,m = map(int,input().split())
    import numpy as np
    ans = np.ones(n+1,dtype=int)*-1
    ans[0] = 1
    mod = 10**9+7
    for _ in range(m):
        a = int(input())
        ans[a]=0
    if ans[1]!=0:
        ans[1]=1
    for i in range(2,n+1):
        if ans[i]!=0:
            ans[i] = (ans[i-1]+ans[i-2])%mod
    print(ans[-1])
        

if __name__ == "__main__":
    main()