program abc113c
    use,intrinsic :: iso_fortran_env
    implicit none
    type ken
        integer(int32), allocatable:: si(:), year(:)
        integer(int32):: i=0
    end type
    integer(int32):: n,m,i,np,ny,j
    integer(int32), allocatable:: ip(:), iy(:), cnt(:), num(:,:)
    type(ken), allocatable:: p(:)


    read*, n,m
    allocate(p(n),cnt(n))
    allocate(ip(m),iy(m), num(2,m))
    cnt(:) = 0
    do i=1,m
        read*, ip(i), iy(i)
        cnt(ip(i))=cnt(ip(i))+1
    end do

    do i=1,n
        allocate(p(i)%si(cnt(i)))
        allocate(p(i)%year(cnt(i)))
    end do

    do i=1,m
        np = ip(i)
        ny = iy(i)
        p(np)%i=p(np)%i+1
        p(np)%si(p(np)%i)=i
        p(np)%year(p(np)%i)=ny
    end do

    do i=1,n
        if (cnt(i) == 0) cycle
        call double_sort(p(i)%year, p(i)%si, 1, cnt(i))
    end do

    do i=1,n
        if (cnt(i) == 0) cycle
        do j=1,cnt(i)
            num(1,p(i)%si(j)) = i
            num(2,p(i)%si(j)) = j
        end do
    end do

    do i=1,m
        print'(2(i0.6))', num(:,i)
    end do
contains

recursive subroutine double_sort(ar1, ar2, fst, lst)
    integer(int32),intent(inout):: ar1(:),ar2(:)
    integer(int32),intent(in):: fst,lst
    integer(int32):: mdl

    if (lst - fst < 2) then
        if (ar1(fst) > ar1(lst)) then
            call swap(ar1(fst), ar1(lst))
            call swap(ar2(fst), ar2(lst))
        end if
        return
    end if

    mdl = (fst+lst)/2

    call double_sort(ar1,ar2,fst,mdl)
    call double_sort(ar1,ar2,mdl+1,lst)
    call double_merge_(ar1,ar2,fst,mdl,lst)
end subroutine


subroutine double_merge_(ar1,ar2,fst,mdl,lst)
    integer(int32),intent(inout):: ar1(:),ar2(:)
    integer(int32),intent(in):: fst,mdl,lst
    integer(int32),allocatable:: t1(:),t2(:)
    integer(int32):: li,ri,ti

    allocate(t1(lst-fst+1), t2(lst-fst+1))

    li=fst
    ri=mdl+1
    ti=1

    do while(li <= mdl .and. ri <= lst)
        if (ar1(li) <= ar1(ri)) then
            t1(ti) = ar1(li) 
            t2(ti) = ar2(li)
            li=li+1
        else
            t1(ti) = ar1(ri)
            t2(ti) = ar2(ri)
            ri=ri+1
        end if
        ti=ti+1
    end do

    if (li <= mdl) then
        t1(ti:) = ar1(li:mdl)
        t2(ti:) = ar2(li:mdl)
    else
        t1(ti:) = ar1(ri:lst)
        t2(ti:) = ar2(ri:lst)
    end if

    ar1(fst:lst) = t1(:)
    ar2(fst:lst) = t2(:)

    deallocate(t1,t2)
end subroutine


subroutine swap(x,y)
    integer(int32),intent(inout):: x,y
    integer(int32):: tmp
    tmp = x
    x = y
    y = tmp
end subroutine




end program abc113c