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

N = int(input())
G = [[-1 for _ in range(N)] for _ in range(N)]
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    G[u - 1][v - 1] = G[v - 1][u - 1] = w % 2

C = [-1 for _ in range(N)]


def dfs(pos, color):
    for i in range(N):
        if C[i] != -1:
            continue
        # even
        if G[pos][i] == 0:
            c = color
            C[i] = c
            dfs(i, c)
        # odd
        elif G[pos][i] == 1:
            c = 1 - color
            C[i] = c
            dfs(i, c)


C[0] = 0
dfs(0, 0)
for i in range(N):
    print(C[i])


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append((v, w))
    G[v].append((u, w))

C = [-1 for _ in range(N)]


def dfs(pos, color):
    C[pos] = color
    for e in G[pos]:
        if C[e[0]] != -1:
            continue
        # odd
        if e[1] & 1:
            c = 1 - color
            dfs(e[0], c)
        # even
        else:
            c = color
            dfs(e[0], c)


dfs(0, 0)
for i in range(N):
    print(C[i])
### BUGGY CODE ###

import sys
import numpy as np

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    alph = ['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']

    pos = [[0 for _ in range(N)] for _ in range(26)]
    for i, c in enumerate(input().strip()):
        p = alph.index(c)
        pos[p][i] = 1

    move = []
    for p in pos:
        move.append(np.array(p))

    cur = np.array([1 for _ in range(N)])
    for _ in range(Q):
        t, d = map(str, input().split())
        p = alph.index(t)
        m = move[p]
        golem = cur * m

        if d == 'L':
            moved_golem = np.append(golem[1:], 0)
        else:
            moved_golem = np.insert(golem[:N-1], 0, 0)

        cur = cur + moved_golem - golem

    print(np.sum(cur))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    S = list(map(str, input().strip()))
    order = [tuple(map(str, input().split())) for _ in range(Q)]
    order = order[::-1]

    left, right = 0, N-1
    for a in order:
        t, d = a[0], a[1]

        if d == 'L':
            if S[left] == t:
                left += 1
                if left > N - 1:
                    return 0

            if right < N - 1 and S[right + 1] == t:
                right = min(N - 1, right + 1)

        else:
            if left > 0 and S[left - 1] == t:
                left = max(0, left - 1)

            if S[right] == t:
                right -= 1
                if right < 0:
                    return 0

    return right - left + 1


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

x = int(input())
i = 1
n= 0
if x % 2 == 0 or x % 5 == 0:
    print(-1)
else:
    for i in range(1, 1000000):

        l = 7 * (10**i - 1) // 9
        n+=1
        if l % x == 0:
            break
    print(n)


### FIXED CODE ###

k = int(input())
a=0
for i in range (1,10**6):
    a=10*a+7
    a%=k
    if a==0:
      ans=i
      break;
    else:
      ans=-1
print(ans)
### BUGGY CODE ###

import numpy as np
H, W = map(int, input().split())
S = [input() for i in range(H)]

# 横
A = np.array([[-10000] * W for i in range(H)])
B = np.array([[-10000] * W for i in range(H)])


for i in range(H):
    jj = 0
    s = 0
    for j in range(W+1):
        if j == W or S[i][j] == '#':
            A[i, jj:j] = s
            s = 0
            jj = j + 1
        else:
            s += 1

for j in range(W):
    ii = 0
    s = 0
    for i in range(H+1):
        if i == H or S[i][j] == '#':
            B[ii:i, j] = s
            s = 0
            ii = i + 1
        else:
            s += 1

X = A + B - 1
print(np.max(X))        


### FIXED CODE ###

H, W = map(int, input().split())
S = [list(input()) for i in range(H)]

# 横
A = [[-10000] * W for i in range(H)]
B = [[-10000] * W for i in range(H)]

for i in range(H):
    jj = 0
    s = 0
    for j in range(W+1):
        if j == W or S[i][j] == '#':
            for x in range(jj, j):
                A[i][x] = s
            s = 0
            jj = j + 1
        else:
            s += 1


for j in range(W):
    ii = 0
    s = 0
    for i in range(H+1):
        if i == H or S[i][j] == '#':
            for y in range(ii, i):
	            B[y][j] = s
            s = 0
            ii = i + 1
        else:
            s += 1

m = 0
for i in range(H):
    for j in range(W):
        m = max(A[i][j] + B[i][j] - 1, m)
            
print(m)
### BUGGY CODE ###

from sys import stdin
f_i = stdin

H, N = map(int, f_i.readline().split())

dp = [10 ** 8] * (H + 10 ** 4)
dp[0] = 0

for i in range(N):
    A, B = map(int, f_i.readline().split())
    for i, t in enumerate(zip(dp, dp[A:H+A]), start=A):
        dp_i, dp_j = t
        dp[i] = min(dp_i + B, dp_j)

print(min(dp[H:]))

### FIXED CODE ###

def solve():
    from sys import stdin
    f_i = stdin
    
    H, N = map(int, f_i.readline().split())
    
    dp = [10 ** 8] * (H + 10 ** 4)
    dp[0] = 0
    
    for i in range(N):
        A, B = map(int, f_i.readline().split())
        for j, t in enumerate(zip(dp, dp[A:H+A]), start=A):
            dp_i, dp_j = t
            if dp_i + B < dp_j:
                dp[j] = dp_i + B
    
    print(min(dp[H:]))

solve()
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    A = [int(a) for a in input().split()]

    score = 1
    for i in range(k):
        score *= A[i]

    for i in range(n - k):
        tmp = ((score // A[i]) * A[k + i])

        if tmp > score:
            print("Yes")
        else:
            print("No")

        score = tmp

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    A = [int(a) for a in input().split()]
        
    for i in range(n - k):
        if A[i + k] > A[i]:
            print("Yes")
        else:
            print("No")

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

N, K = map(int, input().split())
P = list(map(int, input().split()))
P = [sum(range(1, p+1))/p for p in P]
anses = [sum(P[i:i+K]) for i in range(N-K+1)]
print(max(anses))

### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
P = [(1+p)/2 for p in P]

cumsum = [0]*(N+1)
for i in range(1, N+1):
    cumsum[i] = cumsum[i-1] + P[i-1]
ans = 0
for i in range(N-K+1):
    if ans < cumsum[i+K]-cumsum[i]:
        ans = cumsum[i+K]-cumsum[i]
print(ans)
### BUGGY CODE ###

n = int(input())
a = input().split()

b = []
flag = 1
for i in range(n):
    if flag > 0:
        b.append(a.pop(0))
    else:
        b.insert(0, a.pop(0))
    flag *= -1
if flag < 0:
    b.reverse()
for i in b[:-1]:
    print(i+' ', end='')
print(b[-1])


### FIXED CODE ###

from collections import deque

n = int(input())
b = deque()
flag = 1
for i in input().split():
    if flag > 0:
        b.append(i)
    else:
        b.appendleft(i)
    flag *= -1
if flag < 0:
    b.reverse()
print(' '.join(b))
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))

color = []
color.append(a.pop(0))
clen = 1
for ai in a:
    for i, c in enumerate(color): 
        if ai > c:
            color[i] = ai
            #color = quick_sort(color)
            break
        else:
            if i+1 == clen:
                color.append(ai)
                clen += 1
                break
print(clen)

### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
from collections import deque
import bisect

color = deque([a.pop(0)])
color_count =0 
for ai in a: 
    index = bisect.bisect_left(color, ai)
    if index > 0:
        color[index -1] = ai
    else:
        color.appendleft(ai)
print(len(color))
### BUGGY CODE ###

def main():
  #n = int(input())
  #s = input()
  #s = input().split()
  n,k = list(map(int,input().split()))
  #a = list(map(int,input().split()))
  #a = [input() for i in range(n)]
  #a = [int(input()) for i in range(n)]
  #a = [input().split() for i in range(n)]
  #a = [list(map(int,input().split())) for i in range(n)]
  ans = n
  zen = n
  count = 0
  lis = []
  
  if k == 1:
    print(0)
  else:  
    while 1:
      hi = abs(ans-k)
      if hi < zen:
        zen = hi
        ans = hi
        
      else:
        print(ans)
        exit()
      
if __name__ == '__main__':
  main()

### FIXED CODE ###

def main():
  #n = int(input())
  #s = input()
  #s = input().split()
  n,k = list(map(int,input().split()))
  #a = list(map(int,input().split()))
  #a = [input() for i in range(n)]
  #a = [int(input()) for i in range(n)]
  #a = [input().split() for i in range(n)]
  #a = [list(map(int,input().split())) for i in range(n)]
  ans = n
  zen = n
  count = 0
  lis = []
  
  if k == 1:
    print(0)
  elif n <= abs(n-k):
    print(n)
  else:
    ans = n % k
    if ans > 2:
      while 1:
        hi = abs(ans-k)
        if hi < zen:
          zen = hi
          ans = hi

        else:
          print(ans)
          exit()
    else:
      print(ans)
    
      
if __name__ == '__main__':
  main()
### BUGGY CODE ###

class UnionFind:
    def __init__(self, N):
        self.N = N
        self.parents = [-1] * N

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.N) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

N, M = map(int, input().split())
P = list(map(int, input().split()))
UF = UnionFind(N)
for i in range(N):
    P[i] -= 1
for _ in range(M):
    x, y = map(int, input().split())
    x-=1
    y-=1
    UF.union(x, y)

print(sum(len(set(mem)&set(P[i] for i in mem)) for _, mem in UF.all_group_members().items()))

### FIXED CODE ###

N, M = map(int, input().split())
P = list(map(int, input().split()))
for i in range(N):
    P[i] -= 1
T = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    x-=1
    y-=1
    T[x].append(y)
    T[y].append(x)

s1 = set()
def dfs(x):
    s1.add(x)
    s2 = set([x])
    stack = [x]
    while stack:
        u = stack.pop()
        for v in T[u]:
            if v not in s1 and v not in s2:
                s1.add(v)
                s2.add(v)
                stack.append(v)
    return s2

ans = 0
for i in range(N):
    if i in s1:
        continue
    I = dfs(i)
    PI = set(P[i] for i in I)
    ans += len(I.intersection(PI))
print(ans)
### BUGGY CODE ###

N, M = [ int(i) for i in input().strip().split(' ') ]
H    = [ int(i) for i in input().strip().split(' ') ]
paths = [ input().strip().split(' ') for _m in range(M)]
paths = [ [int(p1), int(p2)] for p1, p2 in paths ]
all_paths = []
for path in paths:
    all_paths += path

count = 0
for n in range(1, N+1):
    is_good = 1
    if n not in all_paths:
        count += is_good
        continue

    for path in paths:
        if n not in list(path):
            continue
        if (path[0] == n) and (H[n-1] <= H[path[1]-1]):
            is_good = 0
            break
        if (path[1] == n) and (H[n-1] <= H[path[0]-1]):
            is_good = 0
            break    
    count += is_good
print(count)

### FIXED CODE ###

N, M = [ int(i) for i in input().strip().split(' ') ]
H    = [ int(i) for i in input().strip().split(' ') ]
paths = []
max_neighbor = [ 0 for _ in range(N)]

for _m in range(M):
    path = input().strip().split(' ')
    path = int(path[0]), int(path[1])
    max_neighbor[path[0]-1] = max(max_neighbor[path[0]-1], H[path[1]-1])
    max_neighbor[path[1]-1] = max(max_neighbor[path[1]-1], H[path[0]-1])
count = 0
for n in range(N):
    if max_neighbor[n] < H[n]:
        count += 1
print(count)
### BUGGY CODE ###

import sys
N = int(input())
N = list(map(int,input().split()))
C= 1
if N==0:
    print(0)
    sys.exit()
for i in N:
  C = C*i
  if C > (10 ** 18):
    C=-1
print(C)

### FIXED CODE ###

def mul2():
    n = int(input())
    a = list(map(int, input().split()))
    
    if 0 in a:
        return 0
    ans = 1
    for i in a:
        ans *= i
        if ans > 1000000000000000000:
            return -1
        
    return ans 
print(mul2())
### BUGGY CODE ###

import sys
from pprint import pprint
from collections import deque

sys.setrecursionlimit(4100000)

B = 10


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(N, M, inputs):
    jobs = list(map(string_to_int, inputs))
    jobs.sort(key=lambda x: (x[0]))
    jobs = deque(jobs)

    can_select_jobs = []
    money = 0

    for day in range(1, M + 1):
        while len(jobs) != 0:
            if jobs[0][0] > day:
                break
            else:
                can_select_jobs.append(jobs.popleft())

        if len(can_select_jobs) != 0:
            can_select_jobs.sort(key=lambda x: x[1])
            best_job = can_select_jobs.pop()
            money += best_job[1]

        new_can_select_jobs = []

        while len(new_can_select_jobs) <= M and len(can_select_jobs) != 0:
            new_can_select_jobs.append(can_select_jobs.pop())
        can_select_jobs = new_can_select_jobs
    return money


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    [N, M] = string_to_int(input())
    ret = solve(N, M, inputs(N))
    print(ret)


### FIXED CODE ###

import sys
from pprint import pprint
import heapq

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(N, M, inputs):
    jobs = list(map(string_to_int, inputs))
    jobs.sort(key=lambda x: x[0], reverse=True)
    selectable = []
    money = 0
    for day in range(1, M + 1):
        while len(jobs) != 0 and jobs[-1][0] <= day:
            heapq.heappush(selectable, jobs.pop()[1] * -1)
        if len(selectable) != 0:
            money += heapq.heappop(selectable) * -1
    return money


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    [N, M] = string_to_int(input())
    ret = solve(N, M, inputs(N))
    print(ret)
### BUGGY CODE ###

def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def lm(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def gm(a, b):
    return a * b // lm(a, b)


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()

    l = 1
    res = 0
    for i, a in enumerate(A):
        l2 = gm(l, a)
        res = (res * l2 // l) % mod
        res = (res + l2 // a) % mod
        l = l2
    print(res)


if __name__ == "__main__":
    main()



### FIXED CODE ###

def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def g(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()

    B = 1
    for a in A:
        B *= a // g(B, a)
    
    print(sum(B // a for a in A) % mod)


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

N = int(input())
aA=list(set(int(_) for _ in input().split()))
N = len(aA)
def ggg(i,j):
    if i < j :
        i,j = j,i
    i %= j
    if i == 0:
        return j
    else:
        return ggg(j,i)

if len(aA) == 1:
    print(aA[0])
else:
    iMin = min(aA)
    iMax = max(aA)
    if iMin  == 1:
        print(1)
    else:
        iDm = [i % iMin for i in aA]
        if max(iDm) == 0:
            print(iMin)
            exit()
        else:
            iM = iMax
            for i in range(N):
                iA = aA[i]
                for j in range(i+1,N):
                    iMt = ggg(iA,aA[j])
                    if 0 < iMt and iMt < iM:
                        iM = iMt
                    if iM == 1:
                        print(1)
                        exit()
            print(iM)


### FIXED CODE ###

#gcdか....
def fgcd(a,b):
    while b:
        a,b = b,a%b
    return a

N = int(input())
aA = sorted(set(int(_) for _ in input().split()))
b = aA[0]
for a in aA[1:]:
    b = fgcd(a,b)
print(b)
### BUGGY CODE ###

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


@functools.lru_cache(maxsize=None)
def paint(i, c):  # i = 0, 1, 2
    cost = 0
    for row in range(N):
        for col in range(N):
            if (row + col) % 3 == i:
                cost += D[G[row][col] - 1][c - 1]

    return cost


def cost(comb):
    cost = 0
    for i in range(3):
        cost += paint(i, comb[i])

    return cost


if __name__ == '__main__':
    from itertools import permutations
    N, C = map(int, input().split())
    D = [[int(_) for _ in input().split()] for i in range(C)]
    G = [[int(_) for _ in input().split()] for i in range(N)]
    combs = permutations(range(1, C + 1), 3)
    min_cost = min([cost(comb) for comb in combs])
    print(min_cost)


### FIXED CODE ###

# -*- coding: utf-8 -*-
N, C = map(int, input().split())

D = []
for c in range(C):
    D.append([int(d) for d in input().split()])

Gmod = [[0 for i in range(C)] for i in range(3)]
for n in range(N):
    for m, g in enumerate(input().split()):
        Gmod[(n + m) % 3][int(g) - 1] += 1

K = []
for c0 in range(C):
    d0 = sum([Gmod[0][c] * D[c][c0] for c in range(C)])
    for c1 in [i for i in range(C) if not i == c0]:
        d1 = sum([Gmod[1][c] * D[c][c1] for c in range(C)])
        for c2 in [i for i in range(C) if (not i == c0) and (not i == c1)]:
            d2 = sum([Gmod[2][c] * D[c][c2] for c in range(C)])
            K.append(d0 + d1 + d2)

print(min(K))
### BUGGY CODE ###

import heapq

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
heapq.heapify(A)
for _ in range(M):
    b, c = list(map(int, input().split()))
    for i in range(b):
        if A[0] < c:
            heapq.heappop(A)
            heapq.heappush(A, c)
        else:
            break
print(sum(A))


### FIXED CODE ###

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
D = []
for _ in range(M):
    d = list(map(int, input().split()))
    D.append(d)

A.sort()
D.sort(key=lambda x:x[1], reverse=True)
NewCard = []
for d in D:
    b, c = d
    NewCard += [c] * b
    if(len(NewCard) > N):
        break

i = 0
len_min = min(len(A), len(NewCard))
while i < len_min:
    if A[i] >= NewCard[i]:
        break
    i += 1

print(sum(NewCard[:i]) + sum(A[i:]))
### BUGGY CODE ###

S = input()
N = len(S)
mod = 10**9+7
dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
    if S[i] == "?":
        for d in range(10):
            for k in range(13):
                dp[i+1][(k*10+d)%13] = (dp[i+1][(k*10+d)%13]+dp[i][k])%mod
    else:
        d = int(S[i])
        for k in range(13):
            dp[i+1][(k*10+d)%13] = (dp[i+1][(k*10+d)%13]+dp[i][k])%mod
print(dp[N][5]%mod)

### FIXED CODE ###

S = input()
N = len(S)
mod = 10**9+7
dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
    if S[i] == "?":
        for d in range(10):
            for k in range(13):
                dp[i+1][(k*10+d)%13] = (dp[i+1][(k*10+d)%13]+dp[i][k])%mod
    else:
        d = int(S[i])
        for k in range(13):
            dp[i+1][(k*10+d)%13] = (dp[i+1][(k*10+d)%13]+dp[i][k])%mod
print(dp[N][5]%mod)
### BUGGY CODE ###

S = input()[::-1]
D = [s[::-1] for s in ["dream", "dreamer", "erase", "eraser"]]

i = 0
flg = True
while i < len(S):
  for d in D:
    if S[i:i+len(d)] == d:
      i += len(d)
      break
    flg = False
    break

if flg:
  print('YES')
else:
  print('NO')


### FIXED CODE ###

import re
S = input()

S = re.sub(r'eraser', '', S)
S = re.sub(r'erase', '', S)
S = re.sub(r'dreamer', '', S)
S = re.sub(r'dream', '', S)

if len(S) == 0:
  print('YES')
else:
  print('NO')
### BUGGY CODE ###

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

for i in range(0, len(A)):
    t = t * A[i]

if t > 10**18:
    print("-1")
else:
    print(t)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
t = 1
a = 10 ** 18

if 0 in A:
    t = 0
else:
    for i in A:
        t *= i
        if t > a:
            break

if t > a:
    print("-1")
else:
    print(t)
### BUGGY CODE ###

n = int(input())
s = input()
ck = [0]
cs = [0]
c = 0
for item in s:
    if item != '.':
        c += 1
    cs.append(c)
c = 0
for item in s[::-1]:
    if item != '#':
        c +=  1
    ck.insert(0, c)
ck.insert(0, 0)

temp = [cs[i] + ck[i+1] for i in range(len(s)+1)]

print(min(temp))


### FIXED CODE ###

n = int(input())
s = input()
temp = []
c = 0
pitem = ''
s2 = '.' + s + 'a'
for item in s2:
    if pitem == '' or item == pitem:
        c += 1
        pitem = item
    if item != pitem:
        temp.append(c)
        c = 1
        pitem = item
        continue

# print(temp)
# print(temp2)

t = s2.count('.')
c = 0
c2 = 0
cs = []
for i in range(len(temp)):
    c2 += temp[i]
    if i % 2 == 1:
        c += temp[i]
    cs.append(c + t - (c2 - c))
print(min(cs))
### BUGGY CODE ###

#https://atcoder.jp/contests/abc068/tasks/arc079_a
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
flag = False
tmp = -1
for i in range(M):
    if ab[i][0] == N:
        tmp = ab[i][1]
        for j in range(M):
            if ab[j][0] == tmp and ab[j][1] == 1:
                flag = True
                break
            if ab[j][1] == tmp and ab[j][0] == 1:
                flag = True
                break


    if ab[i][1] == N:
        tmp = ab[i][0]
        for j in range(M):
            if ab[j][0] == tmp and ab[j][1] == 1:
                flag = True
                break
            if ab[j][1] == tmp and ab[j][0] == 1:
                flag = True
                break


if flag:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
lst = [[] for _ in range(N + 1)]
dist = [float("inf")]*(N+1)
for _ in range(M):
    a, b = map(int, input().split())
    lst[a].append(b)
    lst[b].append(a)

q = deque()
d = 0
q.append([1,d])

while q:
    now, d = q.popleft()
    dist[now] = d
    if now == N:
        if d <= 2:
            print("POSSIBLE")
        else:
            print("IMPOSSIBLE")
        exit()
    
    for itm in lst[now]:
        if dist[itm] > d+1:
            q.append([itm,d+1])
            
print("IMPOSSIBLE")
### BUGGY CODE ###

import numpy as np
import math
import sys
n, h = map(int, input().split())
A = np.array([])
B = np.array([])
for _ in range(n):
    a, b = map(int, input().split())
    A = np.append(A, a)
    B = np.append(B, b)

max_a = A.max()
  
C = B[max_a <= B][::-1]

cnt = 0
for c in C:
    if h <= 0:
        break
    cnt += 1
    h -= c

if h > 0:
    cnt += math.ceil(h / max_a)

print(cnt)

### FIXED CODE ###

import numpy as np
import math
import sys
n, h = map(int, input().split())
A = []
B = []
for _ in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

max_a = max(A)
  
C = list(np.array(B)[max_a <= np.array(B)][::-1])
C.sort(reverse=True)

cnt = 0
for c in C:
    if h <= 0:
        break
    cnt += 1
    h -= c

if h > 0:
    cnt += math.ceil(h / max_a)

print(cnt)