#-swank
(unless (member :child-sbcl *features*)
  (quit
   :unix-status
   (process-exit-code
    (run-program *runtime-pathname*
                 `("--control-stack-size" "64MB"
                   "--noinform" "--disable-ldb" "--lose-on-corruption" "--end-runtime-options"
                   "--eval" "(push :child-sbcl *features*)"
                   "--script" ,(namestring *load-pathname*))
                 :output t :error t :input t))))
;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (ql:quickload '(:cl-debug-print :fiveam))
  #-swank (set-dispatch-macro-character #\# #\> (lambda (s c p) (declare (ignore c p)) (read s nil (values) t))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)
#-swank (disable-debugger) ; for CS Academy

;; BEGIN_INSERTED_CONTENTS
(defmacro with-buffered-stdout (&body body)
  "Buffers all outputs to *STANDARD-OUTPUT* in BODY and flushes them to
*STANDARD-OUTPUT* after BODY has been done (without error). Note that only
BASE-CHAR is allowed."
  (let ((out (gensym)))
    `(let ((,out (make-string-output-stream :element-type 'base-char)))
       (let ((*standard-output* ,out))
         ,@body)
       (write-string (get-output-stream-string ,out)))))

(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
  (declare #.OPT)
  (macrolet ((%read-byte ()
               `(the (unsigned-byte 8)
                     #+swank (char-code (read-char in nil #\Nul))
                     #-swank (sb-impl::ansi-stream-read-byte in nil #.(char-code #\Nul) nil))))
    (let* ((minus nil)
           (result (loop (let ((byte (%read-byte)))
                           (cond ((<= 48 byte 57)
                                  (return (- byte 48)))
                                 ((zerop byte) ; #\Nul
                                  (error "Read EOF or #\Nul."))
                                 ((= byte #.(char-code #\-))
                                  (setf minus t)))))))
      (declare ((integer 0 #.most-positive-fixnum) result))
      (loop
        (let* ((byte (%read-byte)))
          (if (<= 48 byte 57)
              (setq result (+ (- byte 48) (* 10 (the (integer 0 #.(floor most-positive-fixnum 10)) result))))
              (return (if minus (- result) result))))))))

(defmacro dbg (&rest forms)
  #+swank
  (if (= (length forms) 1)
      `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
      `(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
  #-swank (declare (ignore forms)))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 (princ obj stream) (terpri stream))))

(defconstant +mod+ 1000000007)

;; Body

(declaim (ftype (function * (values (simple-array list (*)) &optional)) get-spanning-tree))
(defun get-spanning-tree (graph &optional (top 0))
  "Returns a directed spanning tree of GRAPH."
  (declare ((simple-array list (*)) graph)
           ((integer 0 #.most-positive-fixnum) top))
  (let* ((n (length graph))
         (visited (make-array n :element-type 'bit :initial-element 0))
         (result (make-array n :element-type 'list :initial-element nil)))
    (labels ((dfs (v)
               (setf (aref visited v) 1)
               (let (res)
                 (dolist (neighbor (aref graph v))
                   (when (zerop (aref visited neighbor))
                       (push neighbor res)
                       (dfs neighbor)))
                 (setf (aref result v) res))))
      (dfs top))
    result))

(defun main ()
  (let* ((n (read))
         (m (read))
         (graph (make-array n :element-type 'list :initial-element nil)))
    (declare (uint32 n m))
    (dotimes (i m)
      (let ((a (- (read-fixnum) 1))
            (b (- (read-fixnum) 1)))
        (push a (aref graph b))
        (push b (aref graph a))))
    (when (oddp m)
      (println -1)
      (return-from main))
    (let* ((tree (get-spanning-tree graph))
           (tree-edges (make-hash-table :test #'equal))
           (dp (make-hash-table :test #'equal)))
      (dotimes (i n)
        (dolist (neighbor (aref tree i))
          (setf (gethash (cons i neighbor) tree-edges) t)))
      (dotimes (i n)
        (dolist (neighbor (aref graph i))
          (unless (or (gethash (cons i neighbor) tree-edges)
                      (gethash (cons neighbor i) tree-edges)
                      (gethash (cons neighbor i) dp))
            (setf (gethash (cons i neighbor) dp) t))))
      (labels ((dfs (v parent)
                 (let ((count 0))
                   (declare (uint32 count))
                   (dolist (neighbor (aref graph v))
                     (when (gethash (cons v neighbor) tree-edges)
                       (dfs neighbor v))
                     (when (gethash (cons v neighbor) dp)
                       (incf count)))
                   (if (oddp count)
                       (progn (assert (not (= -1 parent)))
                              (setf (gethash (cons v parent) dp) t))
                       (unless (= -1 parent)
                         (setf (gethash (cons parent v) dp) t))))))
        (dfs 0 -1))
      (with-buffered-stdout
        (sb-int:dohash ((key _) dp)
          (format t "~D ~D~%" (+ 1 (car key)) (+ 1 (cdr key))))))))

#-swank (main)


Measured memory_bytes: 78012