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

from collections import defaultdict
from collections import deque
from collections import Counter
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

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 size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    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 group_count(self):
        return len(self.roots())

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

    def depth(self):
    	ans = 0
    	for r in self.roots():
    		ans = max(ans, len(self.members(r)))
    	return ans

n,m = readInts()
ab = []
for i in range(m):
	ab.append(readInts())

uf = UnionFind(n+1)
for a,b in ab:
	uf.union(a,b)

print(uf.depth())


### FIXED CODE ###

from collections import defaultdict
from collections import deque
from collections import Counter
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

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 size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    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 depth(self):
    	ans = 0
    	for r in self.roots():
    		ans = max(ans,self.size(r))
    	return ans

n,m = readInts()
ab = []
for i in range(m):
	ab.append(readInts())

uf = UnionFind(n+1)
for a,b in ab:
	uf.union(a,b)

print(uf.depth())
### BUGGY CODE ###

[N, M] = list(map(int, input().split(' ')))
card_list = list(map(int, input().split(' ')))

card_list.sort()

C_list = [0] * N
for i in range(M):
  [B, C] = list(map(int, input().split(' ')))
  if C_list[0] > C:
    continue
  else:
    for k in range(B):
      if C > card_list[k] and C_list[k] < C:
        C_list[k] = C
      else:
        break
    C_list.sort()
  
C_list.sort()

ans = 0
count = 0
for i in range(N):
  if card_list[-1] > C_list[-1]:
    ans += card_list.pop()
    count += 1
  else:
    ans += C_list.pop()
    count += 1
      
print(ans) 

### FIXED CODE ###

[N, M] = list(map(int, input().split(' ')))
card_list = list(map(int, input().split(' ')))

card_list.sort()
compare_list = []

for i in range(M):
  (B, C) = list(map(int, input().split(' ')))
  compare_list.append((C,B))
    
compare_list.sort()

ans = 0
for i in range(N):
  if compare_list == []:
    ans += sum(card_list[i:])
    break
  if card_list[-1] > compare_list[-1][0]:
    ans += card_list.pop()
  elif compare_list[-1][1] > 0:
    ans += compare_list[-1][0]
    tmp = compare_list.pop()
    a = tmp[0]
    b = tmp[1]
    if b != 1:
      compare_list.append((a,b-1)) 
      
print(ans)
### BUGGY CODE ###

import sys
import numpy as np
sys.setrecursionlimit(500000)

def f(i):
    if memo[i] != float("Inf"):return memo[i]

    for j in range(1,k+1):
        if i - j >= 0:
            memo[i] = min(memo[i],f(i-j)+abs(ary[i-j]-ary[i]))
    return memo[i]
n,k = map(int,input().split())
ary = list(map(int,input().split()))
ary = np.array(ary)
memo = np.array([np.inf for _ in range(n)])
memo[0] = 0
print(int(f(n-1)))

### FIXED CODE ###

import numpy as np

n, k = map(int,input().split())
h = list(map(int,input().split()))

h = np.array(h)
dp = np.zeros(n, dtype=int)

for i in range(1,n):
    m = max(0,i-k)
    dp[i] = min(dp[m:i] + np.abs(h[i] - h[m:i]))
print(dp[n-1])
### BUGGY CODE ###

n = int(input())
l = [int(input()) for i in range(n)]
for i in l:
  if i == max(l):
    print(sorted(l)[-2])
  else:
    print(max(l))


### FIXED CODE ###

n = int(input())
l = [int(input()) for i in range(n)]
a = max(l)
b = sorted(l)[-2]
for i in l:
  print(b if i == a else a)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input() 
data = [ tuple(map(int, input().split())) for _ in range(Q) ] 

counter = [0 for _ in range(Q)]
index = -1
while True:
	index = S.find("AC", index+1)

	if index == -1:
		break
	
	for i, (l, r ) in enumerate(data):
		if l-1 <= index < r-1:
			counter[i] += 1


for res in counter:
	print(res)



# print(indexList)

# for (l, r) in data:
	# print(indexList[l-1: r-1])
	# print(sum(indexList[l-1: r-1]))

### FIXED CODE ###

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

t = [0] * (N + 1) 

for i in range(N):
	t[i+1] = t[i] + (1 if S[i:i+2] == "AC" else 0)

for i in range(Q):
	l, r = map(int, input().split())
	print(t[r-1] - t[l-1])
### BUGGY CODE ###

from math import gcd
#a,bの最大公約数
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

#リスト l の最大公約数
def gcdlist(l):
    a = l[0]
    for i in range(len(l)):
        a = gcd(a,l[i])
    return a
n = int(input())
A = list(map(int, input().split()))
ans = 0

for i in range(n):
    tmp = A.copy()
    tmp.pop(i)
    gcd_num = gcdlist(tmp)
    ans = max(ans, gcd_num)

print(ans)

### FIXED CODE ###

from math import gcd
#リスト l の最大公約数
def gcdlist(l):
    a = l[0]
    for i in range(len(l)):
        a = gcd(a,l[i])
    return a
n = int(input())
A = list(map(int, input().split()))
ans = 0

x = [0]*n
y = [0]*n
for i in range(1, n):
    x[i] = gcd(x[i-1], A[i-1])
for i in reversed(range(n-1)):
    y[i] = gcd(y[i+1], A[i+1])

for i in range(n):
    tmp = gcd(x[i], y[i])
    ans = max(ans, tmp)

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

#coding: utf-8
from collections import defaultdict
import sys

H, W, M = (int(x) for x in input().split())

NH = [[0, i] for i in range(H)]
NW = [[0, i] for i in range(W)]

B = []
for i in range(M):
    h, w = (int(x)-1 for x in input().split())
    B.append((h, w))
    NH[h][0] += 1
    NW[w][0] += 1

NH.sort(reverse=True)
NW.sort(reverse=True)
maxH = NH[0][0]
maxW = NW[0][0]

for i in range(H):
    countH, idxH = NH[i] 
    if countH != maxH:
        break

    for j in range(W):
        countW, idxW = NW[j] 
        if countW!= maxW:
            break

        if (idxH, idxW) not in B:
            print(maxH + maxW)
            sys.exit(0)

print(maxH + maxW - 1)



### FIXED CODE ###

#coding: utf-8
from collections import defaultdict
import sys

H, W, M = (int(x) for x in input().split())

NH = [[0, i] for i in range(H)]
NW = [[0, i] for i in range(W)]

B = defaultdict(int) 
for i in range(M):
    h, w = (int(x)-1 for x in input().split())
    B[(h, w)] = 0
    NH[h][0] += 1
    NW[w][0] += 1

NH.sort(reverse=True)
NW.sort(reverse=True)
maxH = NH[0][0]
maxW = NW[0][0]

for i in range(H):
    countH, idxH = NH[i] 
    if countH != maxH:
        break

    for j in range(W):
        countW, idxW = NW[j] 
        if countW!= maxW:
            break

        if (idxH, idxW) not in B:
            print(maxH + maxW)
            sys.exit(0)

print(maxH + maxW - 1)
### BUGGY CODE ###

n, k = map(int, input().split())
num_list = list(map(int, input().split()))
cnt = 0
cnt_list = []
ans = 0

for i in set(num_list):
    for j in num_list:
        if i == j:
            cnt += 1
    cnt_list.append(cnt)
    cnt = 0

dic = dict(zip(set(num_list), cnt_list))
dic_sorted = sorted(dic.items(), key=lambda x: x[1])
del_num = dic_sorted[:len(dic_sorted)-k]

for i in del_num:
    ans += i[1]

print(ans)


### FIXED CODE ###

import collections

n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 0

list_a = list(collections.Counter(a).values())
dic = dict(zip(collections.Counter(a), list_a))
dic_sorted = sorted(dic.items(), key=lambda x: x[1])
del_num = dic_sorted[:len(dic_sorted)-k]

for i in del_num:
    ans += i[1]

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

n=int(input())
l=[int(i) for i in input().split()]
from collections import Counter 
c=Counter(l) 
ans=[]
for i in set(l): 
    if c[i]>=2:
        ans=ans+[i]*(c[i]//2)
ans.sort(reverse=1)
if len(ans)<=1:
    print(0)
else: 
    print(ans[0]*ans[1])

### FIXED CODE ###

n=int(raw_input())
l=[int(i) for i in raw_input().split()]
from collections import Counter 
c=Counter(l) 
ans=[]
for i in c: 
    if c[i]>=2:
        ans=ans+[i]*(c[i]//2)
ans.sort(reverse=1)
if len(ans)<=1:
    print(0)
else: 
    print(ans[0]*ans[1])
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
A=[list(map(int,input().split())) for i in range(q)]
for l,r in A:
    t=s[l-1:r]
    cnt=0
    for i in range(len(t)-1):
        if t[i]+t[i+1]=="AC":
            cnt +=1
    print(cnt)

### FIXED CODE ###

n,q=map(int,input().split())
s=input()+"P"
A=[list(map(int,input().split())) for i in range(q)]
B=[0]*(n+1)
cnt=0
for i in range(1,n):
    if s[i-1]+s[i]=="AC":cnt +=1
    B[i+1]=cnt

for l,r in A:print(B[r]-B[l])
### BUGGY CODE ###

import re
import numpy as np

H,W,K = map(int,input().split())
grid = []
for i in range(H):
  S = input()
  grid.append( [S[i] for i in range(W) ])
grid = np.array(grid,dtype='int64')

min_cnt = 1000*10+1
#横の区切りを作る
for j in range(2**(H-1)):
  cnt = 0
  #二進数の文字列を取得
  bin_str = format(j,"0{}b".format(H-1)) 
  #区切りのインデックスリスト
  l_p =[0]+[ x.start()+1 for x in re.finditer("1",bin_str) ] +[H]

  #cntに区切りの分だけ付け加える
  cnt = cnt + len(l_p)-2
  
  #決めた行の区切りに対して、列ごとの和の配列を取得
  L = np.empty((0,W),int)
  for i in range(len(l_p)-1):
    slice_wa = [np.sum(grid[l_p[i]:l_p[i+1],:],axis=0)]
    L = np.append(L, slice_wa ,axis=0)

  tate = np.zeros( len(l_p)-1 ,dtype='int64')
  for w in range(W):#k以上の要素があるか
    tate = tate + L[:,w]
    if True in (tate > K):
      cnt = cnt + 1
      tate = np.zeros( len(l_p)-1 ,dtype='int64')+L[:,w]   
      
  min_cnt = min(cnt,min_cnt)   

###
print(min_cnt)

### FIXED CODE ###

import re

H,W,K = map(int,input().split())
grid = [[0 for i in range(W+1)]]
for i in range(H):
  S = input()
  grid.append([0]+[ int(S[i]) for i in range(W) ])

#累積和gridの作成
#行について
for i in range(H+1):
  for j in range(W):
    grid[i][j+1] += grid[i][j]
#列について
for j in range(W+1):
  for i in range(H):
    grid[i+1][j] += grid[i][j]   

min_cnt = (H-1)*(W-1)
#横の区切りを作る
for h in range(2**(H-1)):
  cnt = 0
  #二進数の文字列を取得
  bin_str = format(h,"0{}b".format(H-1)) 
  #区切りのインデックスリスト
  l_p =[1]+[ x.start()+2 for x in re.finditer("1",bin_str) ] +[H+1]

  #cntに区切りの分だけ付け加える
  cnt = cnt + len(l_p) - 2
  
  ws = 0
  for w in range(1,W+1):
    for k in range(len(l_p)-1):
      if grid[l_p[k+1]-1][w]-grid[l_p[k+1]-1][w-1] > K:
        min_cnt=(H-1)*(W-1)+1
      if grid[l_p[k+1]-1][w]- (grid[l_p[k]-1][w]+grid[l_p[k+1]-1][ws]-grid[l_p[k]-1][ws]) > K:
        cnt = cnt + 1
        ws = w-1
        break    
  min_cnt = min(min_cnt,cnt)

###
print(min_cnt)
### BUGGY CODE ###

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

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

banks = tuple(tuple(map(int, input().split())) for _ in range(n))

max_s = 50 * (n-1)

s = min(s, max_s)

import heapq

h = []
dp = [[float('inf')] * (max_s+1) for _ in range(n)]
ans = [float('inf')] * n

heapq.heappush(h, (0, 0, s))
while h:
    time, node, coin = heapq.heappop(h)
    if time < dp[node][coin]:
        dp[node][coin] = time
    if time < ans[node]:
        ans[node] = time

    c, d = banks[node]
    if coin < max_s:
        heapq.heappush(h, (time+d, node, min(coin + c, max_s)))

    for n, a, b in edges[node]:
        new_time = time + b
        new_coin = coin - a
        if new_coin < 0 or new_time >= dp[n][new_coin]:
            continue
        heapq.heappush(h, (new_time, n, new_coin))

for a in ans[1:]:
    print(a)


### FIXED CODE ###

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

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

banks = tuple(tuple(map(int, input().split())) for _ in range(n))

max_s = 50 * (n-1)

s = min(s, max_s)

import heapq

h = []
dp = [[float('inf')] * (max_s+1) for _ in range(n)]
ans = [float('inf')] * n

heapq.heappush(h, (0, 0, s))
while h:
    time, node, coin = heapq.heappop(h)
    if time >= dp[node][coin]:
        continue
    dp[node][coin] = time
    if time < ans[node]:
        ans[node] = time

    c, d = banks[node]
    if coin < max_s:
        heapq.heappush(h, (time+d, node, min(coin + c, max_s)))

    for n, a, b in edges[node]:
        new_time = time + b
        new_coin = coin - a
        if new_coin < 0 or new_time >= dp[n][new_coin]:
            continue
        heapq.heappush(h, (new_time, n, new_coin))

for a in ans[1:]:
    print(a)
### BUGGY CODE ###

s = input()
q = int(input())
arr = [list(input().split()) for i in range(q)]

for i in arr:
    if i[0] == '1':
        s = s[::-1]
    else:
        if i[1] == '1':
            s = i[2] + s
        else:
            s = s + i[2]
print(s)

### FIXED CODE ###

s = input()
q = int(input())
arr = [list(input().split()) for i in range(q)]
mae1 = 0
mae = []
ato = []
for i in arr:
    if i[0] == '1':
        mae1 = 0 if mae1 == 1 else 1
    else:
        if mae1 == 0:
            if i[1] == '1':
                mae.append(i[2])
            else:
                ato.append(i[2])
        else:
            if i[1] == '1':
                ato.append(i[2])
            else:
                mae.append(i[2])
mae = ''.join(mae)
ato = ''.join(ato)
ans = mae[::-1] + s + ato
if mae1 == 1:
    ans = ans[::-1]
print(ans)
### BUGGY CODE ###

n = int(input())
st = input()
l = []
for i in range(n):
    temp = st[i]
    east = [0 if i == "E" else 1 for i in st[:i]]
    west = [0 if i == "W" else 1 for i in st[i+1:]]
    l.append(sum(east) + sum(west))
print(min(l))

### FIXED CODE ###

from collections import Counter
n = int(input())
st = input()
l = []
stc = Counter(st)
ma = [Counter(st[:0])["W"] + Counter(st[1:])["E"]]
previous = st[0]
for i in range(1,n):
    temp = ma[-1]
    if(previous == "W"):
        temp+=1
    previous = st[i]
    if(st[i] == "E"):
        temp-=1
    ma.append(temp)
print(sorted(ma)[0])
### BUGGY CODE ###

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

ans = '-1 -1 -1'

count_max = Y / 1000  # all 1000
ans_list = []


for i in reversed(range(Y // 10000 + 1)):
    count_tmp1 = count_max - 9 * i
    price_tmp1 = Y - 10000 * i
    if count_tmp1 < N or price_tmp1 < 0:
        continue

    if count_tmp1 == N:
        ans = '{} {} {}'.format(i, 0, N - i)
        #ans_list.append(ans)
        break

    is_continue = True
    for j in reversed(range(price_tmp1 // 5000 + 1)):
        count_tmp2 = count_tmp1 - 4 * j
        price_tmp2 = price_tmp1 - 5000 * j
        if count_tmp2 < N or price_tmp2 < 0:
            continue
        if count_tmp2 == N:
            ans = '{} {} {}'.format(i, j, N - i -j)
            # ans_list.append(ans)
            is_continue = False
            break
    if not is_continue:
        break
print(ans)
#print(ans_list)

### FIXED CODE ###

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

count_max = Y / 1000  # all 1000

ans = '-1 -1 -1'
for i in range(N+1):  # 10000
    for j in range(N+1 - i):  # 5000
        k = N - i - j
        if k < 0:
            continue
        total = 10000 * i + 5000 * j + 1000 * k
        if total == Y:
            ans = '{} {} {}'.format(i, j, k)
            break
print(ans)
### BUGGY CODE ###

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

inf = 10**9
magic = []
c = 0
for i in range(n):
	a, b = map(int, input().split())
	magic.append([a,b])
	c = max(c,a)

dp = [inf] * (h+c)

for i, j in magic:
	dp[i] = min(dp[i],j)

for i in range(len(dp)):
	for j in range(n):
		if i - magic[j][0] <= 0 or dp[i-magic[j][0]] == inf:
			continue
		else:
			dp[i] = min(dp[i],dp[i-magic[j][0]] + magic[j][1])

print (min(dp[h:]))


### FIXED CODE ###

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

inf = 10**9
magic = []
c = 0
for i in range(n):
	a, b = map(int, input().split())
	magic.append([a,b])
	c = max(c,a)

dp = [inf] * (h+c)

for i, j in magic:
	dp[i] = min(dp[i],j)

for i in range(len(dp)):
	for j in range(n):
		if i - magic[j][0] <= 0 or dp[i-magic[j][0]] == inf:
			continue
		else:
			dp[i] = min(dp[i],dp[i-magic[j][0]] + magic[j][1])

print (min(dp[h:]))
### BUGGY CODE ###

X = int(input())
 
ans = 0
p = 2
for i in range(X):
  p = 1
  while(True):
    p += 1
    if(i ** p <= X):
      tmp = i ** p
      pass
    else:
      break
  if(ans<tmp):
    ans = tmp
  if(p == 2):
    break
  
print(ans)

### FIXED CODE ###

X = int(input())
 
ans = 1
p = 2
A = set()
for i in range(2,X):
  if(i in A):
    continue
  p = 1
  while(True):
    p += 1
    power = i ** p
    if(power <= X):
      A.add(power)
      tmp = power
      pass
    else:
      break
  if(ans<tmp):
    ans = tmp
  if(p == 2):
    break
  
print(ans)
### BUGGY CODE ###

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

R=S.count("R")
G=S.count("G")
B=S.count("B")

ans=R*G*B
for i in range(1,N-1):
    for j in range(i+1,N):
        if S[i-1]==S[j-1]:continue
        n=2*j-i
        if n>=N+1:continue
        if S[i-1]!=S[n-1] and S[j-1]!=S[n-1]:
            ans-=1

print(ans)

### FIXED CODE ###

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

Lis=[[] for _ in range(3)]
RGB="RGB"

for i in range(N):
    idx=RGB.index(S[i])
    Lis[idx].append(i+1)

if len(Lis[0])==0 or len(Lis[1])==0 or len(Lis[2])==0:
    print(0)
    exit()

Ng=len(Lis[2])
ans=0
for r in Lis[0]:
    for g in Lis[1]:
        n1=2*r-g
        n2=2*g-r
        n3=(r+g)//2
        Su=Ng
        if N>=n1>0:
            if S[n1-1]=="B":
                Su-=1
        if N>=n2>0:
            if S[n2-1]=="B":
                Su-=1
        if (g-r)%2==0:
            if S[n3-1]=="B":
                Su-=1
        ans+=Su
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

from collections import deque


if __name__ == '__main__':

    n = int(input())
    A = [[float("inf") for j in range(n)] for i in range(n)]

    for i in range(n - 1):
        A[i][i] = 0
        s, t, d = map(int, input().split())
        A[s][t] = d
        A[t][s] = d

    Q = deque()

    def bfs(s):
        d = [float("inf")] * n
        Q.append(s)
        d[s] = 0
        while Q:
            u = Q.popleft()
            for v in range(n):
                if d[v] == float("inf"):
                    d[v] = d[u] + A[u][v]
                    Q.append(v)

        return d

    d = bfs(0)
    tgt = d.index(max(d))
    d = bfs(tgt)
    print(max(d))



### FIXED CODE ###

# -*- coding: utf-8 -*-

from collections import deque


if __name__ == '__main__':

    n = int(input())
    E = [set() for _ in range(n)]
    for _ in range(n - 1):
        s, t, d = map(int, input().split())
        E[s].add((t, d))
        E[t].add((s, d))

    Q = deque()

    def bfs(s):
        d = [float("inf")] * n
        Q.append(s)
        d[s] = 0
        while Q:
            u = Q.popleft()
            for v, w in E[u]:
                if d[v] == float("inf"):
                    d[v] = d[u] + w
                    Q.append(v)

        return d

    d = bfs(0)
    tgt = d.index(max(d))
    d = bfs(tgt)
    print(max(d))
### BUGGY CODE ###

arr = input().split()
n = int(arr[0])
m = int(arr[1])

a = [0] * m
b = [0] * m

for i in range(m):
    tmp = input().split()
    a[i] = int(tmp[0])
    b[i] = int(tmp[1])

mat = [[0] * n for i in range(n)]

for i in range(m):
    mat[a[i]-1][b[i]-1] = 1
    mat[b[i]-1][a[i]-1] = 1

path = []
for i in range(n):
    if mat[0][i] == 1:
        path.append(i)

flag = False
for i in range(len(path)):
        if mat[path[i]][n-1] == 1: 
            flag = True

if flag == True:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
    


### FIXED CODE ###

arr = input().split()
n = int(arr[0])
m = int(arr[1])

x = []
y = []

for i in range(m):
    a,b = map(int, input().split())
    if a == 1:
        x.append(b)
    if b == n:
        y.append(a)

if len(set(x+y)) < len(x) + len(y):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

from collections import Counter 
N = int(input())
numbers = [int(i) for i in input().split()]

c = Counter(numbers)

divisors = sorted(set(numbers))
target_numbers = sorted([k for k, v in c.items() if v == 1])

cnt = N - len(target_numbers)
for n in target_numbers:
    for d in divisors:
        if n == d:
            continue
        if n % d == 0:
            cnt += 1
            break
        if n /2 < d:
            break
            
print(N - cnt)

### FIXED CODE ###

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

d = set()
s = set()

for n in numbers:
    if n in s: 
        d.add(n)
    else :
        s.add(n) 

M = max(s) 

X = [1 for _ in range(M+1)] 

for a in s:
    if a in d:
        X[a] = 0 
    for i in range(2*a, M+1, a): 
        X[i] = 0
    
output = 0

for n in numbers:
    if X[n] == 1:
        output += 1
print(output)
### BUGGY CODE ###

import numpy as np

D = int(input())
c = np.array(list(map(int, input().split())))
s = np.array([list(map(int, input().split())) for _ in range(D)])


def score(D, c, s, t):
    score = 0

    last_date = np.zeros(26)

    for di in range(1, D + 1):
        score += s[di - 1][t[di - 1]]

        last_date[t[di - 1]] = di

        for i in range(26):
            score -= c[i - 1] * (di - last_date[i - 1])

    return int(score)


def f5(D, c, s):
    t = np.zeros(D, dtype=int)
    for di in range(1, D + 1):
        current_score = score(D, c, s, t)

        random_values = np.arange(26)
        np.random.shuffle(random_values)
        limit = 5

        for i in random_values[:limit]:
            tmp = np.copy(t)
            tmp[di - 1] = i
            tmp_score = score(D, c, s, tmp)
            if current_score < tmp_score:
                t = tmp
                break
    return t


for ti in f5(D, c, s):
    print(ti + 1)

### FIXED CODE ###

import numpy as np

D = int(input())
c = np.array(list(map(int, input().split())))
s = np.array([list(map(int, input().split())) for _ in range(D)])

for si in s:
    print(np.where(si==max(si))[0][0].tolist() + 1)