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

s=input()
ans=0
for i in range(0,len(s)-1):
    for j in range(i+1,len(s)):
        if int((s[i:j+1]))%2019==0:
            ans=ans+1
print(ans)
    
   

### FIXED CODE ###

s=list(input())
s=s[::-1]
l=len(s)
mod=2019
count=[0]*2019
count[0]=1
num=0
seki=1
for i in range(l):
    num+=int(s[i])*seki
    num=num%mod
    count[num]+=1
    seki=(seki*10)%mod
ans=0
for i in range(2019):
    N=count[i]
    ans+=N*(N-1)//2
print(ans)
### BUGGY CODE ###

N, W = map(int, input().split())
ws = [0] * N
vs = [0] * N

for i in range(N):
  ws[i], vs[i] = map(int, input().split())

import numpy as np
dp_table = np.zeros((N+1,W+1))

for i in range(1,N+1):
  for w_now in range(1,W+1):
    if w_now - ws[i-1] >= 0:
      dp_table[i, w_now] = max( dp_table[i-1 , w_now], dp_table[ i-1, w_now-ws[i-1] ] + vs[i-1] )
    else:
      dp_table[i, w_now] = dp_table[i-1 , w_now]
print(int(dp_table[-1, -1]))

### FIXED CODE ###

N, W = map(int, input().split())
ws = [0] * N
vs = [0] * N

for i in range(N):
  ws[i], vs[i] = map(int, input().split())

dp_table = [[0]*(W+1) for _ in range(N+1)]

for i in range(1,N+1):
  for w_now in range(1,W+1):
    if w_now - ws[i-1] >= 0:
      dp_table[i][w_now] = max( dp_table[i-1][w_now], dp_table[ i-1][w_now-ws[i-1] ] + vs[i-1] )
    else:
      dp_table[i][w_now] = dp_table[i-1][w_now]
print(int(dp_table[-1][-1]))
### BUGGY CODE ###

tmp=input()
l=[int(tmp[i:]) for i in reversed(range(len(tmp)))]
cnt=[0]*2019
cnt[0] = 1
for i in l:
   cnt[i%2019] += 1
import collections
ans=0
for i in cnt:
   if i > 1:
      ans+=i*(i-1)//2
print(ans)

### FIXED CODE ###

import sys
tmp=sys.stdin.readline().rstrip()
def main():
   ans=0
   cnt=[0]*2019
   cnt[0]+=1
   t=0
   d=1
   for i in reversed(tmp):
      t=(t+int(i)*d)%2019
      cnt[t]+=1
      d=d*10%2019
   for i in cnt:
      ans+=i*(i-1)//2
   print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

H, W = map(int, input().split())

a = []
for i in range(H):
    a.append(str(input()))

R = [[0] * W for i in range(H)]
L = [[0] * W for i in range(H)]
D = [[0] * W for i in range(H)]
U = [[0] * W for i in range(H)]

for i in range(H):
    cur = 0
    for j in range(W):
        if a[i][j] == "#":
            cur = 0
            U[i][j] = 0
        else:
            cur += 1
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] += U[i-1][j] + 1
        L[i][j] = cur

ans = 0
for i in reversed(range(H)):
    cur = 0
    for j in reversed(range(W)):
        if a[i][j] == "#":
            cur = 0
            D[i][j] = 0
        else:
            cur += 1
            if i == (H-1):
                D[i][j] = 1
            else:
                D[i][j] += D[i+1][j] + 1
        R[i][j] = cur
        if L[i][j] + R[i][j] + D[i][j] + U[i][j] -3 > ans:
            ans = L[i][j] + R[i][j] + D[i][j] + U[i][j] -3

print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline

H, W = map(int, input().split())

a = []
for i in range(H):
    a.append(str(input()))

R = [[0] * W for i in range(H)]
L = [[0] * W for i in range(H)]
D = [[0] * W for i in range(H)]
U = [[0] * W for i in range(H)]

for i in range(H):
    cur = 0
    for j in range(W):
        if a[i][j] == "#":
            cur = 0
            U[i][j] = 0
        else:
            cur += 1
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] += U[i-1][j] + 1
        L[i][j] = cur

ans = 0
for i in reversed(range(H)):
    cur = 0
    for j in reversed(range(W)):
        if a[i][j] == "#":
            cur = 0
            D[i][j] = 0
        else:
            cur += 1
            if i == (H-1):
                D[i][j] = 1
            else:
                D[i][j] += D[i+1][j] + 1
        R[i][j] = cur
        if L[i][j] + R[i][j] + D[i][j] + U[i][j] -3 > ans:
            ans = L[i][j] + R[i][j] + D[i][j] + U[i][j] -3

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

def main():
    N, M = list(map(int, input().split()))
    A = []
    for i in range(M):
        A.append(int(input()))

    mod = 1000000007

    dp = [0] * (N+1)
    dp[0] = 1
    for now in range(0, N):
        for next in range(now+1, min(N, now+2)+1):
            if next not in A:
                dp[next] += dp[now]
                #dp[next] %= mod

    print(dp[N] % mod)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N, M = list(map(int, input().split()))
    A = set()
    for i in range(M):
        A.add(int(input()))

    mod = 1000000007

    dp = [0] * (N+1)
    dp[0] = 1
    for now in range(0, N):
        for next in range(now+1, min(N, now+2)+1):
            if next not in A:
                dp[next] += dp[now]
                dp[next] %= mod

    print(dp[N] % mod)

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

from collections import Counter
n = int(input())
res = list(map(int,input().split()))
sums = 0
ans = []
for i in range(len(res)):
    popl = res.pop(i)
    a = Counter(res)
    sums = 0
    for j in a.values():
        sums += j * (j - 1) // 2
    ans.append(sums)
    res.insert(i,popl)
for k in ans:
    print(k)

### FIXED CODE ###

from collections import Counter
n = int(input())
res = list(map(int,input().split()))
a = Counter(res)

sums = 0

for i in a.values():
    sums +=  i * (i - 1) // 2

for j in res:
    print(sums - a[j] * (a[j] -1) //2 + (a[j]-1) * (a[j] -2 ) // 2)
### BUGGY CODE ###

import numpy as np

N = int(input())
A = [int(a) for a in input().split()]

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x % 998244353
        x *= x % 998244353
        n //= 2

    return K * x % 998244353

if A[0] != 0:
    print(0)
    exit()
if A.count(0) != 1:
    print(0)
    exit()

k = max(A)

R = [1]
result = 1


for i in range(k):
    R.append(A.count(i + 1))

for j in range(k):
    result *= pow_k(R[j], R[j + 1])

    # if R[j + 1] % 2 == 0:
    #     result *= ((R[j] ** 2 % 998244353) ** (R[j + 1] // 2)) % 998244353
    # else:
    #     result *= R[j] * ((R[j] ** 2 % 998244353) ** (R[j + 1] // 2)) % 998244353

    result %= 998244353

    if result == 0:
        print(0)
        exit()

print(result % 998244353)


### FIXED CODE ###

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

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x % 998244353
        x *= x % 998244353
        n //= 2

    return K * x % 998244353


R = [0] * (k + 1)
result = 1
for i in A:
    R[i] += 1

if A[0] != 0 or R[0] != 1:
    print(0)
    exit()

for j in range(k):
    result *= pow_k(R[j], R[j + 1])

    if result == 0:
        print(0)
        exit()

print(result % 998244353)
### BUGGY CODE ###

n = int(input())
from collections import defaultdict
d = defaultdict(list)
X = []
xl = [tuple(map(int,input().split())) for i in range(n)]
for x,l in xl:
    d[x].append(x-l)
    d[x].append(x+l)
    X.append(x)

X.sort()

i = 1

while len(X)>i:
    x_1 = X[i-1]
    x_2 = X[i]
    min_1 , max_1 = d[x_1]
    min_2 , max_2 = d[x_2]

    if max_1 > min_2:
        if max_2 >= max_1:
            d.pop(x_2)
            X.pop(i)
            i -= 1
        else:
            d.pop(x_1)
            X.pop(i-1)
            i -= 1

    i += 1
ans = len(d)
print(ans)


### FIXED CODE ###

n = int(input())
from collections import defaultdict
d = defaultdict(list)
X = []
xl = [tuple(map(int,input().split())) for i in range(n)]
for x,l in xl:
    d[x].append(x-l)
    d[x].append(x+l)
    X.append(x)

X.sort()


n_remove = 0


for i in range(1,n):
    x_1 = X[i-1]
    x_2 = X[i]
    min_1 , max_1 = d[x_1]
    min_2 , max_2 = d[x_2]

    if max_1 > min_2:
        n_remove += 1
        if max_2 >= max_1:
            d[x_2] = d[x_1]
            X[i] = X[i-1]


ans = n - n_remove
print(ans)
### BUGGY CODE ###

N = int(input())

# {1, 2, ..., N}
# {P1, P2, ..., Pn}　として {2, 3, ..., N, 1} を選べる

count = 0
for i in range(N):
  count += i
  
print(count)

### FIXED CODE ###

N = int(input())

# {1, 2, ..., N}
# {P1, P2, ..., Pn}　として {2, 3, ..., N, 1} を選べる

print((N-1) * N // 2)
### BUGGY CODE ###

import math

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

def f7(seq):
    seen = set()
    seen_add = seen.add
    return [ x for x in seq if x not in seen and not seen_add(x)]

a_unique = f7(a)

d = 0

for ai in a_unique:
    ni = a.count(ai)
    if ni < ai:
        d += ni
    else:
        d += ni - ai

print(d)



### FIXED CODE ###

import math

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

#リストから重複を取り除く
def f7(seq):
    seen = set()
    seen_add = seen.add
    return [ x for x in seq if x not in seen and not seen_add(x)]

d = 0

a_unique = {}

for i in range(0,len(a)):
    if a[i] in a_unique:
        a_unique[a[i]] += 1
    else:
        a_unique[a[i]] = 1

for ai in a_unique.keys():
    if a_unique[ai] >= ai:
        d += a_unique[ai] - ai
    else:
        d += a_unique[ai]

print(d)
### BUGGY CODE ###

a,b,k=map(int,input().split());r=range(a,b+1)
for i in sorted(set(r)-set(r[k:-k])):print(i)

### FIXED CODE ###

a,b,k=map(int,input().split())
s=list((range(a,b+1)[:k]))
t=list(range(a,b+1)[-k:])
for r in sorted(set([s,s+t][b>k])):print(r)
### BUGGY CODE ###

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

ok = [1 for i in range(len(A))]

for i in range(len(A)-1):
  for j in range(i+1, len(A)):
    if A[j] % A[i] == 0:
      ok[j] = 0
    if A[j] == A[i]:
      ok[i] = 0

print(sum(ok))

### FIXED CODE ###

N = int(input())
*A,=map(int,input().split())
A = sorted(A)

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

flag = [0]*(10**6+5)
for i in range(N):
  flag[A[i]] = 1

for i in range(N):
  if flag[A[i]] == 0:
    continue
  if i>0 and A[i]==A[i-1]:
    flag[A[i]] = 0
    continue
  for num in range(A[i]*2,A[-1]+1,A[i]):
    flag[num] = 0
  
print(sum(flag))
### BUGGY CODE ###

from collections import defaultdict

n = int(input())
s = input()
passwords = defaultdict(int)
for i in range(1000):
    num = str(i)
    password = "0" * (3 - len(num)) + num
    #print(password)
    for j in range(n):
        if s[j] == password[0]:
            #print("OK1", password)
            for k in range(j + 1, n):
                if s[k] == password[1]:
                    #print("OK2")
                    for l in range(k + 1, n):
                        if s[l] == password[2]:
                            #print("OK3", password)
                            passwords["".join(password)] += 1
                            break
                
                    break
            break

print(len(passwords))

### FIXED CODE ###

N = int(input())
S = input()

ans = 0
for i in range(1000):
    num = str(i).zfill(3)
    if S.find(num[0]) == -1:
        continue
    S1 = S[S.find(num[0]) + 1:]
    if S1.find(num[1]) == -1:
        continue
    S2 = S1[S1.find(num[1]) + 1:]
    if S2.find(num[2]) == -1:
        continue
    ans += 1

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

def gcd(x,y):
    if y == 0: return x
    else: return gcd(y,x%y)

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

n = int(input())
a = [int(i) for i in input().split()]
ans = 0
mod = 10**9+7
l = a[0]
for i in range(1,n):
    l = lcm(l,a[i])

for i in range(n):
    ans += l//a[i]
    ans %= mod

print(ans)

### FIXED CODE ###

def gcd(x,y):
    if y == 0: return x
    else: return gcd(y,x%y)

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

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

ans = 0
mod = 10**9+7
l = a[0]
for i in range(1,n):
    l = lcm(l,a[i])

for i in range(n):
    ans += l//a[i]

print(ans%mod)
### BUGGY CODE ###

K, S = map(int, input().split())
count = 0
for i in range(K + 1):
    for j in range(K + 1):
        for k in range(K + 1):
            if i + j + k == S:
                count = count + 1

print(count)


### FIXED CODE ###

K, S = map(int, input().split())
count = 0
for x in range(K + 1):
    for y in range(K + 1):
        z = S - x - y
        if 0 <= z <= K:
            count = count + 1

print(count)
### BUGGY CODE ###

from numpy.linalg import matrix_power

mod = 10 ** 9 + 7
class mint:
    def __init__(self, i):
        self.i = i % mod
    def __add__(self, other):
        return mint(self.i + other.i)
    def __mul__(self, other):
        return mint(self.i * other.i)
    def __str__(self):
        return str(self.i)

N, K = map(int, input().split())
A = [[mint(int(i)) for i in input().split()] for _ in range(N)]

print(matrix_power(A, K).sum())

### FIXED CODE ###

from numpy import array, eye

mod = 10 ** 9 + 7

N, K, *A = map(int, open(0).read().split())
A = array(A, dtype=object).reshape(N, N)

ans = eye(N, dtype=object)
while K:
    if K & 1:
        ans = (ans.dot(A)) % mod
    A = A.dot(A) % mod
    K //= 2

print(ans.sum() % mod)
### BUGGY CODE ###

K=int(input())
A=[1,2,3,4,5,6,7,8,9]
I=1
while I<=K:
    B=A.pop(0)
    if not B%10==0:
        A.append(B%10+10*B-1)
    A.append(B%10+10*B)
    if not B%10==9:
        A.append(B%10+10*B+1)
    I+=1
print(B)

### FIXED CODE ###

K=int(input())
A=[1,2,3,4,5,6,7,8,9]
I=0
while I<=K:
    if not A[I]%10==0:
        A.append(A[I]%10+10*A[I]-1)
    A.append(A[I]%10+10*A[I])
    if not A[I]%10==9:
        A.append(A[I]%10+10*A[I]+1)
    if len(A)>=K:
      break
    I+=1
print(A[K-1])
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    visited[Th][Tw] = 1
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()


### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    visited[Th][Tw] = 1
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()
### BUGGY CODE ###

S = input()
dp = [[0]*13 for _ in [0]*-~len(S)]
dp[0][0] = 1
mod = 10**9 + 7

for i, s in enumerate(S):
    if s == '?':
        d = dp[i+1]
        for j in range(13):
            for k in range(10):
                x = (j*10+k) % 13
                d[x] = (d[x] + dp[i][j]) % mod
    else:
        for j in range(13):
            dp[i+1][(j*10+int(s)) % 13] = dp[i][j]
print(dp[-1][5] % mod)


### FIXED CODE ###

S = input()
dp = [[0]*13 for _ in [0]*-~len(S)]
dp[0][0] = 1
mod = 10**9 + 7

for i, s in enumerate(S):
    if s == '?':
        d = dp[i+1]
        for j in range(13):
            for k in range(10):
                x = (j*10+k) % 13
                d[x] = (d[x] + dp[i][j]) % mod
    else:
        for j in range(13):
            dp[i+1][(j*10+int(s)) % 13] = dp[i][j]
print(dp[-1][5] % mod)
### BUGGY CODE ###

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

i=1
a = i**N

while a<=P:
    if P%a == 0:
        ans = i
    i = i+1
    a = i**N
    
print(ans)

### FIXED CODE ###


N,P=map(int,input().split())
if N==1:
    print(P)
    exit()
elif P==1:
    print(1)
    exit()

PO=P
K=[0]*(int(P**0.5)+1)

for i in range(2,int(P**0.5)):
    while P%i==0:
        K[i]+=1
        P=P//i
    K[i]=K[i]//N
    if P==1:
        break

ans=1
for i in range(2,int(PO**0.5)):
    if K[i]!=0:
        ans*=i**K[i]

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

N = int(input())
ans = 0
for i in range(1,N ):
	ans += i
print(ans)

### FIXED CODE ###

N = int(input())
ans = (N * (N - 1)) // 2
print(int(ans))
### BUGGY CODE ###

import sys

S=sys.stdin.readline()
l=len(S)

mod=10**9+7

a=0
ab=0
ans=0
all=1

for i in range(l):
	if S[i]=="A":
		a+=all
	elif S[i]=="B":
		ab+=a
	elif S[i]=="C":
		ans+=ab
	elif S[i]=="?":
		ans = ans*3 + ab
		ab = ab*3 + a
		a = a*3 + all
		all *= 3

	ans%=mod
	ab%=mod
	a%=mod
	all%mod


print ans


### FIXED CODE ###

S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-


def xyz(x, y, z):
    return x**2 + y**2 + z**2 + x * y + y * z + z * x


def main():
    N = int(input())
    # print(N)

    for i in range(1, N + 1):
        ans = 0
        for x in range(1, i):
            if x**2 > i:
                break
            for y in range(1, i):
                if y**2 > i:
                    break
                for z in range(1, i):
                    if z**2 > i:
                        break
                    if i == xyz(x, y, z):
                        ans += 1
        print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
    N = int(input())
    ans = [0] * (6 * 10**4 + 10)

    for x in range(1, 101):
        for y in range(1, 101):
            for z in range(1, 101):
                ans[x**2 + y**2 + z**2 + x * y + y * z + x * z - 1] += 1

    for i in range(N):
        print(ans[i])


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

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

r = s.count('R')
g = s.count('G')
b = s.count('B')

# 1つ目の条件を満たす
first_conditions = r*g*b
# 1つ目の条件は満たすが、2つ目の条件は満たさない
second_condition = 0
# 2つ目の条件を満たすということは、(i,j,k)のときk=2j-i
for i in range(n-2):
    for j in range(i+1,n-1):
        if 2*j-i<n and s[i]!=s[2*j-i] and s[j]!=s[2*j-i] and s[i]!=s[j]:
            second_condition += 1
print(first_conditions-second_condition)

### FIXED CODE ###

n = int(input())
s = input()
r_ary = []
g_ary = []
b_ary = []
for i in (s):
    if i == 'R':
        r_ary.append(i)
    elif i == 'G':
        g_ary.append(i)
    elif i == 'B':
        b_ary.append(i)
r = len(r_ary)
g = len(g_ary)
b = len(b_ary)
first_conditions = r*g*b
for i in range(n-2):
    for j in range(i+1,n-1):
        if 2*j-i<n and s[i]!=s[2*j-i] and s[j]!=s[2*j-i] and s[i]!=s[j]:
            first_conditions -= 1
print(first_conditions)
### BUGGY CODE ###

N = int(input())
A = []
for n in range(N):
    A.append(input())
A.sort()
B = []
for n in range(N):
    C = 0
    for i in range(N):
        if A[n] == A[i]:
            C += 1
    B.append(C)
m = max(B)
D = []
for i in range(N):
    if m <= B[i]:
        D.append(A[i])
D = list(set(D))
for i in range(len(D)):
    print(D[i])

### FIXED CODE ###

N = int(input())
A = {}
B = []
for n in range(N):
    a = input()
    B.append(a)
    A[a] = 0
for n in range(N):
    A[B[n]] += 1
res = 0
C = []
for key, value in A.items():
    if res < value:
        res = value
for key, value, in A.items():
    if res <= value:
        C.append(key)
C.sort()
for c in C:
    print(c)
### BUGGY CODE ###

# グラフわからんのでグラフアルゴリズム忘れた
# dfsでやる 限度2回

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


def dfs(t, c, used):
    if c != 0 and t == n - 1:
        return True
    if c == 0:
        return False
    flag = False
    for g in graph[t]:
        if g in used:
            continue
        next_used = used[:]
        next_used.append(g)
        flag = dfs(g, c - 1, next_used)
        if flag:
            break
    return flag


for x in graph[0]:
    if dfs(x, 2, []):
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")


### FIXED CODE ###

# グラフわからんのでグラフアルゴリズム忘れた
# dfsでやる 限度2回c
# なんかしらんけどdfsが2TLEになるので諦めた それぞれの島について1とNがあれば良い

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

for g in graph[1 : n - 1]:
    c = 0
    for v in g:
        if c >= 2:
            break
        if v == 0 or v == n - 1:
            c += 1
    if c == 2:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")