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

n=int(input())
data_set=[0 for i in range(n)]
for i in range(n):
    a=list(map(int,input().split()))
    a.append(-1)
    data_set[i]=a
index=[0 for i in range(n)]
ans=-1
flag=True
now=[data_set[i][index[i]] for i in range(n)]
finished=[False for i in range(n)]
while flag:
    visited=[False for i in range(n)]
    sub=False
    for i in range(n):
        #nowリストのうち日ありからi+1番目のものについての一致条件の確認
        K=now[i]
        if now[K-1]==i+1 and not(visited[i] or visited[K-1]) and not(finished[i] or finished[K-1]):
                    visited[i]=True
                    visited[K-1]=True
                    index[i]+=1
                    index[K-1]+=1
                    sub=True
                    if index[i]==n-1:
                        finished[i]=True             
                    now[i]=data_set[i][index[i]]
                    if index[K-1]==n-1:
                        finished[K-1]=True                   
                    now[K-1]=data_set[K-1][index[K-1]]
    if not sub:
        flag=False
    ans+=1
judge=True
for i in range(n):
  if finished[i]==False:
    judge=False
    break
if judge:
  print(ans)
else:
  print(-1)

### FIXED CODE ###

n=int(input())
import time
T=time.time()
data_set=[0 for i in range(n)]
for i in range(n):
    a=list(map(int,input().split()))
    a.append(-1)
    data_set[i]=a
index=[0 for i in range(n)]
ans=-1
flag=True
semi=False
now=[data_set[i][index[i]] for i in range(n)]
finished=[False for i in range(n)]
while flag:
    visited=[False for i in range(n)]
    sub=False
    for i in range(n):
        #nowリストのうち日ありからi+1番目のものについての一致条件の確認
        K=now[i]
        if now[K-1]==i+1 and not(visited[i] or visited[K-1]) and not(finished[i] or finished[K-1]):
                    visited[i]=True
                    visited[K-1]=True
                    index[i]+=1
                    index[K-1]+=1
                    sub=True
                    if index[i]==n-1:
                        finished[i]=True             
                    now[i]=data_set[i][index[i]]
                    if index[K-1]==n-1:
                        finished[K-1]=True                   
                    now[K-1]=data_set[K-1][index[K-1]]
    if not sub:
        flag=False
    if time.time()-T>1.5:
        flag=False
        semi=True
    ans+=1
judge=True
for i in range(n):
  if finished[i]==False:
    judge=False
    break
if judge:
  print(ans)
else:
  if not semi:
    print(-1)
  if semi:
    print(499500)
### BUGGY CODE ###

import queue
n, m, k = map(int,input().split())
frnd = [[] for i in range(n+1)]
blck = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    frnd[a].append(b)
    frnd[b].append(a)

for i in range(k):
    c,d = map(int,input().split())
    blck[c].append(d)
    blck[d].append(c)

#グラフをグループ化するやつ
def grouping(n,arr):
    gr = []
    al = [-1 for i in range(n+1)]
    q = queue.Queue()
    for i in range(1,n+1):
        if al[i] == 0:
            continue
        else:
            gi = []
            q.put(i)
            al[i] = 0
            while not q.empty():
                qi = q.get()
                gi.append(qi)
                for ai in arr[qi]:
                    if al[ai] < 0:
                        q.put(ai)
                        al[ai] = 0
            gr.append(gi)
    return gr

fg = grouping(n,frnd)

gn = [0 for i in range(n+1)]
for i,g in enumerate(fg):
    for p in g:
        gn[p] = i

ans = [0 for i in range(n)]
for i in range(1,n+1):
    num = 0
    for pi in fg[gn[i]]:
        if pi == i or pi in frnd[i] or pi in blck[i]:
            continue
        else:
            num += 1
    ans[i-1] = num

print(" ".join(map(str,ans)))


### FIXED CODE ###

'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    n,m,k = map(int,ipt().split())
    fl = [[] for i in range(n)]
    bl = [set() for i in range(n)]
    for i in range(m):
        a,b = map(int,ipt().split())
        fl[a-1].append(b-1)
        fl[b-1].append(a-1)
    for i in range(k):
        c,d = map(int,ipt().split())
        bl[c-1].add(d-1)
        bl[d-1].add(c-1)

    ans = [-1]*n
    al = [True]*n
    for i in range(n):
        if al[i]:
            q = [i]
            al[i] = False
            st = set([i])
            while q:
                qi = q.pop()
                for j in fl[qi]:
                    if al[j]:
                        st.add(j)
                        al[j] = False
                        q.append(j)
            lst = len(st)
            for j in st:
                tmp = lst-len(fl[j])-1
                for k in bl[j]:
                    if k in st:
                        tmp -= 1
                ans[j] = tmp

    print(" ".join(map(str,ans)))


    return None

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

A,B=map(int, input().split())

if A==B:
	print(A)
	exit(0)
ans=A^(A+1)
for i in range(A+2,B+1):
	ans=ans^i
print(ans)

### FIXED CODE ###

A,B=map(int, input().split())

# if A==B:
# 	print(A)
# 	exit(0)
# ans=A^(A+1)
# for i in range(A+2,B+1):
# 	ans=ans^i
# print(ans)

# A,B=0,456

# if A==B:
# 	print(A)
# 	exit(0)
# ans=A^(A+1)
# print(1, bin(ans))
# for i in range(A+2,B+1):
# 	ans=ans^i
# 	print(i, bin(ans))

if A==B:
	print(A)
	exit(0)

def func(c):
	if c%2==1:
		if c%4==1:
			return 1
		else:
			return 0
	else:
		if (c-1)%4==1:
			return 1^c
		else:
			return 0^c
print(func(A-1)^func(B))
### BUGGY CODE ###

import sys
import numpy as np

input = sys.stdin.readline

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

def knapsack(N, W):
    Weight, V = [], []
    for i in range(N):
        w, v = map(int, input().split())
        Weight.append(w)
        V.append(v)

    dp = np.zeros((N+1, W+1))

    maximum = 0
    for i in range(N):
        for w in range(W+1):
            if w >= Weight[i]:
                dp[i+1, w] = dp[i, w - Weight[i]] + V[i]
                maximum = max(maximum, dp[i+1, w])
            else:
                dp[i+1, w] = dp[i, w]
            
    print(int(maximum))

knapsack(N, W)


### FIXED CODE ###

N, W = map(int, input().split())
#i個目の品物までで重さw以下のときの価値の最大値 
dp = [[0]*(W+1) for _ in range(N+1)]
"""
dp[i, wi:W+1] = max(i番目の重さwiの品物を入れた場合, 入れなかった場合)
         = np.max(dp[i-1, :W-wi+1] + v, dp[i-1, wi:W+1])
"""

for i in range(1, N+1):
    w, v = map(int, input().split())

    for j in range(W+1):
        if j - w >= 0:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
        else:
            dp[i][j] = dp[i-1][j]

print(dp[-1][-1])
### BUGGY CODE ###

N, Q = map(int, input().split())
G = [[] for _ in range(N)]
ans = [0]*N

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

for _ in range(Q):
    p, x = map(int, input().split())
    ans[p-1] += x

judge = [0]
queue = [0]
while queue:
    a = queue.pop()
    for i in G[a]:
        if i not in judge:
            judge.append(i)
            ans[i] += ans[a]
            if G[i]:
                queue.append(i)

print(*ans)


### FIXED CODE ###

N, Q = map(int, input().split())
G = [[] for _ in range(N)]
ans = [0]*N

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

for _ in range(Q):
    p, x = map(int, input().split())
    ans[p-1] += x

judge = [False]*N
judge[0] = True
queue = [0]
while queue:
    a = queue.pop()
    for i in G[a]:
        if not judge[i]:
            judge[i] = True
            ans[i] += ans[a]
            if G[i]:
                queue.append(i)

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

def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
k = int(input())
s = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        a = gcd(i,j)
        for z in range(1,k+1):
            s+=gcd(a,z)
print(s)

### FIXED CODE ###

from math import gcd
k = int(input())
s = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        a = gcd(i,j)
        for z in range(1,k+1):
            s+=gcd(a,z)
print(s)
### BUGGY CODE ###

from operator import mul
from functools import reduce
n = input()
l = (int(e) for e in input().split(" "))
res = 1
res = reduce(mul,l)
if res > 1e+18:
    print("-1")
else:
    print(res)

### FIXED CODE ###

from operator import mul
from functools import reduce
n = input()
tmp = input().split(" ")
l = sorted([int(e) for e in tmp])
def solve():
    res = 1
    for e in l:
        res = e*res
        if res > 1e+18:
            print("-1")
            return
    print(res)
solve()
### BUGGY CODE ###

K = int(input())
count = 1
a='7'
if K%2==0:
  print('-1')
else:
  while int(a)%K!=0:
    count += 1
    a = a + '7'
  print(count)

### FIXED CODE ###

K = int(input())
if K==7 or K==1:
  print(1)
else:
  count = 1
  x = 7%K
  for i in range(K):
    x = (x*10+7)%K
    count += 1
    if x==0:
      print(count)
      break
  if x!=0:
    print(-1)
### BUGGY CODE ###

N,K=map(int,input().split())
if(N<K):
  K=N
h=list(map(int,input().split()))
dp=[10000000000000 for i in range(N)]
dp[0]=0
for i in range(1,N):
  for j in range(K+1):
    dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
print(dp[N-1])                      
                      
                      
                  
      

### FIXED CODE ###

N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*N
for i in range(1,N):
    dp[i]=min(dp[j]+abs(h[i]-h[j]) for j in range(max(0,i-K),i))
print(dp[N-1])
### BUGGY CODE ###

import sys

sys.setrecursionlimit(500000)

def input() -> str:
    return sys.stdin.readline().rstrip()

def f(i, j):
    if j <= 0:
        return 0
    if i < 0 and j > 0:
        return float("inf")
    if (i, j) not in dp:
        dp[(i, j)] = min([f(i - 1, j - k * ab[i][0]) + k * ab[i][1] for k in range((h - 1) // ab[i][0] + 2)])
    return dp[(i, j)]

h, n = map(int, input().split())
ab = sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda x: -x[0])
dp = dict()
print(f(n - 1, h))

### FIXED CODE ###

import sys

def input() -> str:
    return sys.stdin.readline().rstrip()

h, n = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]
m = max(a for a, _ in ab)
dp = [0] * (h + m * 2 + 1)
for i in range(-m, h + m + 1):
    if i <= 0:
        dp[i] = 0
    else:
        dp[i] = min(dp[i - a] + b for a, b in ab)
print(min(dp[h:h + m + 1]))
### BUGGY CODE ###

L, R = map(int, input().split())
ans = 2019
for i in range(L, R):
    for j in range(i + 1, R + 1):
        if i * j % 2019 < ans:
            ans = i * j % 2019
    if ans == 0:
        break
print(ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!
L, R = map(int, input().split())
ans = 2019
for i in range(L, R):
    for j in range(i + 1, R + 1):
        if i * j % 2019 < ans:
            ans = i * j % 2019
        if ans == 0:
            break
    if ans == 0:
        break
print(ans)
### BUGGY CODE ###

n=input()
n=int(n)
arrstr=input()
ans=0
for no in range(1000):
    no=str(no);
    no=no.zfill(3)
    suc=0
    poi=0
    for i in range(len(arrstr)):
        if(arrstr[i]==no[poi]):
            poi+=1
            if poi==3:
                suc=1
                break
             
    if suc:ans+=1
print(ans)

### FIXED CODE ###

n=input()
n=int(n)
arrstr=input()
ans=0
for no in range(1000):
    no=str(no);
    no=no.zfill(3)
    suc=0
    poi=0
    for i in range(len(arrstr)):
        if(arrstr[i]==no[poi]):
            poi+=1
            if poi==3:
                suc=1
                break
             
    if suc:ans+=1
print(ans)
### BUGGY CODE ###

import collections

input_d1 = int(input())
input_d2 = list(input().split())

c = collections.Counter(input_d2)

for i in input_d2:
    summ = 0
    for j in c.keys():
        if i == j:
            summ += (c[j]-2) * (c[j]-1) / 2
        else:
            summ += (c[j]-1) * c[j] / 2
    print(int(summ))

### FIXED CODE ###

input_d1 = int(input()) 
input_d2 = list(input().split())

c = sorted(input_d2)
c.append('0')
e = {'0':0}
g = [0]
s = 0

for i in range(0,input_d1):
    if c[i] == c[i+1]:
        pass
    else:
        g.append(i+1)
        e[c[i]] = i + 1 - g[s]
        s += 1

e.pop('0')
d = {}
f = sum(map(lambda x:x*(x-1)/2 , e.values()))

for i in e.keys():
    d[i] = 1 - e[i] + f


for i in input_d2:
    print(int(d[i]))
### BUGGY CODE ###

x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
lisa.sort(reverse=True)
lisb.sort(reverse=True)
lisc.sort(reverse=True)
an = []
ans = []
for num in lisb:
    for nu in lisa:
        an.append(num+nu)
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for num in lisc:
    for nu in an:
        ans.append(num+nu)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])


### FIXED CODE ###

x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
lisa.sort(reverse=True)
lisb.sort(reverse=True)
lisc.sort(reverse=True)
an = []
ans = []
for num in lisb:
    for nu in lisa:
        an.append(num+nu)
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for num in lisc:
    for nu in an:
        ans.append(num+nu)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

# A - Darker and Darker
import numpy as np

H,W = map(int,input().split())
h,w = np.arange(H,dtype=int),np.arange(W,dtype=int)
A = [list(input()) for _ in range(H)]
B = np.zeros((H,W),dtype=int)

queue = []

for i in h:
    for j in w:
        if A[i][j]=='#':
            queue.append((i,j))

while queue!=[]:
    I,J = queue.pop(0)
    for i,j in [(I-1,J),(I+1,J),(I,J-1),(I,J+1)]:
        if (i in h) and (j in w) and A[i][j]=='.' and B[i][j]==0:
            B[i][j] = B[I][J]+1
            queue.append((i,j))

print(np.max(B))

### FIXED CODE ###

# A - Darker and Darker
from collections import deque

H,W = map(int,input().split())
B = [[-1] * W for _ in range(H)]

queue = deque([])

for i in range(H):
    A = input()
    for j in range(W):
        if A[j]=='#':
            B[i][j] = 0
            queue.append((i,j))

ans = 0

while queue:
    I,J = queue.popleft()
    for di,dj in ((-1,0),(1,0),(0,-1),(0,1)):
        i,j = I+di,J+dj
        if 0<=i<H and 0<=j<W:
            if B[i][j]<0:
                B[i][j] = B[I][J]+1
                ans = max(ans,B[i][j])
                queue.append((i,j))

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

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

numlist = {}
for i in A:
    if i in numlist:
        numlist[i] += 1
    else:
        numlist[i] = 1
numbers = numlist.values()
numbers = sorted(numbers)

change = 0
while len(numbers) > K:
    change += numbers[0]
    del numbers[0]
print(change)


### FIXED CODE ###

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

numlist = {}
for i in A:
    if i in numlist:
        numlist[i] += 1
    else:
        numlist[i] = 1
numbers = numlist.values()
numbers = sorted(numbers)

change = 0
vari = len(numbers)
for i in range(vari):
    if K >= vari - i:
        break
    change += numbers[i]

print(change)
### BUGGY CODE ###

N=int(input())
print(0)
S0 = input()[0]
if S0=="V":exit()
print(N-1)
if input()[0]=="V":exit()

r,l=0,N-1
while r-l>1:
    med=(r+l)//2
    print(med)
    S1=input()[0]
    if S1=="V":
        exit()
    elif (med%2==0 and S1==S0) or (med%2==1 and S1!=S0):
        r=med
    else:
        l=med
print(r)


### FIXED CODE ###

N=int(input())
print(0)
S0 = input()[0]
if S0=="V":exit()
print(N-1)
if input()[0]=="V":exit()

l,r=0,N-1
while r-l>1:
    med=(r+l)//2
    print(med)
    S1=input()[0]
    if S1=="V":
        exit()
    elif (med%2==0 and S1==S0) or (med%2==1 and S1!=S0):
        l=med
    else:
        r=med
print(r)
### BUGGY CODE ###

import numpy as np
n, m = map(int, input().split())

matrix = np.array([[0 for i in range(n)] for i in range(n)])
for i in range(m):
    a, b = map(int, input().split())
    matrix[a-1][b-1] = 1
    matrix[b-1][a-1] = 1

print(matrix.sum(axis=1).max()+1)

### FIXED 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 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())

      
from collections import Counter
n, m = map(int, input().split())

uf = UnionFind(n)
for i in range(m):
    a, b = map(int, input().split())
    uf.union(a-1,b-1)

print(abs(min((uf.parents))))
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
count = 0
for i in range(N+1):
  for j in range(N+1):
    ai = a[i:j]
    if ai == []:
      count = count - 1
    go = sum(ai)
    if go == 0:
      count += 1
count = int(count)
print(count) 

### FIXED CODE ###

from collections import Counter
N = int(input())
a = list(map(int, input().split()))
count = 0
s = list()
s.append(0)
for i in range(N):
  s.append(a[i] + s[i])
for j in  Counter(s).values():
  count += (j * (j-1))/2
print(int(count))
### BUGGY CODE ###

n = int(input())
perputation = list(map(int, input().split()))
cnt = 1

if n == 1:
    print("1")
else:
    for i in range(1, n):
        part = []
        for j in range(i):
            part.append(perputation[j])
        if min(part) >= perputation[i]:
            cnt += 1
    print(cnt)

### FIXED CODE ###

n = int(input())
perputation = list(map(int, input().split()))
cnt = 1
last_min = perputation[0]

if n == 1:
    print("1")
else:
    for i in range(1, n):
        if last_min >= perputation[i]:
            cnt += 1
            last_min = perputation[i]
    print(cnt)
### BUGGY CODE ###

def main():
    inf = float('inf')
    n,k=map(int,input().split())
    h = list(map(int,input().split()))
    dp=[0] + [inf] *(n-1)#初期化
    for i in range(1,n):
        for j in range(1,k+1):#iからj離れた場所から来る場合と比較
            if i >=j:
                dp[i] = min(dp[i],abs(h[i-j]-h[i])+dp[i-j])
            else:break
    print(dp[n-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    inf = float('inf')
    n,k=map(int,input().split())
    h = list(map(int,input().split()))
    dp=[0] + [inf] *(n-1)#初期化
    for i in range(1,n):
        for j in range(1,k+1):#iからj離れた場所から来る場合と比較
            if i >=j:
                dp[i] = min(dp[i],abs(h[i-j]-h[i])+dp[i-j])
            else:break
    print(dp[n-1])

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

import math

k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            ans+=(math.gcd(i,math.gcd(j,l)))
print(ans)

### FIXED CODE ###

from math import gcd

k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            ans+=(gcd(i,gcd(j,l)))
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
d = {}
array = []
for _ in range(N):
    a, b = map(int, input().split())
    if a in array:
        d[a] += b
    else:
        d[a] = b
        array.append(a)

array.sort()
counter = 0
for i in array:
    counter += d[i]
    if counter >= K:
        print(i)
        break

### FIXED CODE ###

N, K = map(int, input().split())
array = [0 for _ in range(10**5)]
for _ in range(N):
    a, b = map(int, input().split())
    array[a-1] += b

num = 0
for i in range(len(array)):
    num += array[i]
    if num >= K:
        print(i+1)
        break
### BUGGY CODE ###

import sys
input = sys.stdin.readline
 
N, M = (int(i) for i in input().split())
input_list = [[int(i) for i in input().split()] for i in range(M)] 
 
m_list = [[] for j in range(N+1)]
 
for inputs in input_list:
    m_list[inputs[0]].append(inputs[1])
 
for arr in m_list:
    arr.sort()
 
for inputs in input_list:
    num = m_list[inputs[0]].index(inputs[1]) + 1
    print(str(inputs[0]).zfill(6) + str(num).zfill(6))

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
N, M = (int(i) for i in input().split())
py_list = [[int(i) for i in input().split()] + [0] for i in range(M)] 
m_list = [[] for j in range(N+1)]
 
sorted_py_list = sorted(py_list, key=lambda x:x[1])

city_list = {}
for py in sorted_py_list:
    city_list[py[0]] = city_list[py[0]]+1 if py[0] in city_list else 1
    py[2] = city_list[py[0]]
 
for py in py_list:
    print(str(py[0]).zfill(6) + str(py[2]).zfill(6))
### BUGGY CODE ###

def remove(s):
    r = None
    for i in range(len(s)-1):
        if s[i] != s[i+1]:
            r = s[0:i] + s[i+2:]
            break
    return r


def calc(s):
    count = 0
    c = s
    while True:
        t = remove(c)
        if t == None:
            break
        count += 2
        c = t
    return count


s = input()
print(calc(s))


### FIXED CODE ###

s = input()
print(2*min(s.count('0'), s.count('1')))
### BUGGY CODE ###

n,m = map(int,input().split())
all_li = []
ma = {}
for _ in range(m):
    p,y = map(int,input().split())
    all_li.append((p,y))
    if p in ma:
        ma[p].append(y)
    else:
        ma[p] = [y]
#print(all_li)
#[[1, 32], [2, 63], [1, 12]]
#print(ma)
# {1: [32, 12], 2: [63]}
sorted_li = [[] for _ in range(n)]
for k,v in ma.items():
    sorted_li[k-1] = list(sorted(v))
#print(ma)
for a in all_li:
    count = sorted_li[a[0]-1].index(a[1]) + 1
    print(str(a[0]).zfill(6)+str(count).zfill(6))

### FIXED CODE ###

from bisect import bisect_right
n,m = map(int,input().split())
all_li = []
ma = {}
for _ in range(m):
    p,y = map(int,input().split())
    all_li.append((p,y))
    if p in ma:
        ma[p].append(y)
    else:
        ma[p] = [y]
#print(all_li)
#[[1, 32], [2, 63], [1, 12]]
#print(ma)
# {1: [32, 12], 2: [63]}
sorted_li = [[] for _ in range(n)]
for k,v in ma.items():
    sorted_li[k-1] = list(sorted(v))
#print(ma)
for a in all_li:
    #print(a[1],sorted_li[a[0]-1])
    count = bisect_right(sorted_li[a[0]-1],a[1],)
    #count = sorted_li[a[0]-1].index(a[1]) + 1
    print(str(a[0]).zfill(6)+str(count).zfill(6))
### BUGGY CODE ###

n,m=map(int,input().split())
ab=[]
for i in range(m):
  a,b=map(int,input().split())
  ab.append((a,b))
#print(ab)
     
mid=[]
for (i,j) in ab:
  if i==1:
    mid.append(j)

for (i,j) in ab:
  if i in mid and j==n:
    print("POSSIBLE");exit()
    
print("IMPOSSIBLE")

    

### FIXED CODE ###

n,m=map(int,input().split())
c=[]
d=[]
for i in range(m):
  a,b=map(int,input().split())
  if a==1:
    c.append(b)
  if b==n:
    d.append(a)
#O(m)
if len(set(c)&set(d))!=0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")