#-swank
(unless (member :child-sbcl *features*)
  (quit
   :unix-status
   (process-exit-code
    (run-program *runtime-pathname*
                 `("--control-stack-size" "256MB"
                   "--noinform" "--disable-ldb" "--lose-on-corruption" "--end-runtime-options"
                   "--eval" "(push :child-sbcl *features*)"
                   "--script" ,(namestring *load-pathname*))
                 :output t :error t :input t))))
(in-package :cl-user)
(eval-when (:compile-toplevel :load-toplevel :execute)
  (sb-int:defconstant-eqx opt
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0))
    #'equal)
  #+swank (ql:quickload '(:cl-debug-print :fiveam) :silent t)
  #-swank (set-dispatch-macro-character
           #\# #\> (lambda (s c p) (declare (ignore c p)) `(values ,(read s nil nil t)))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)

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

(defconstant +mod+ 1000000007)

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

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

;; BEGIN_INSERTED_CONTENTS
;;;
;;; Topological sort
;;; Reference:
;;; https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search
;;;

(defpackage :cp/topological-sort
  (:use :cl)
  (:export #:cycle-detected-error #:topological-sort))
(in-package :cp/topological-sort)

(define-condition cycle-detected-error (error)
  ((graph :initarg :graph :reader cycle-detected-error-graph)
   (vertex :initarg :vertex :reader cycle-detected-error-vertex))
  (:report
   (lambda (condition stream)
     (format stream "Detected a cycle containing ~A in ~A."
             (cycle-detected-error-vertex condition)
             (cycle-detected-error-graph condition)))))

(declaim (ftype (function * (values (simple-array (integer 0 #.most-positive-fixnum) (*)) &optional))
                topological-sort)
         (inline topological-sort))
(defun topological-sort (graph)
  "Returns a vector of all the vertices sorted in topological order. This
function signals CYCLE-DETECTED-ERROR when it detects a cycle.

GRAPH := vector of adjacency lists."
  (declare (vector graph))
  (let* ((n (length graph))
         (tmp-marked (make-array n :element-type 'bit :initial-element 0))
         (marked (make-array n :element-type 'bit :initial-element 0))
         (result (make-array n :element-type '(integer 0 #.most-positive-fixnum)))
         (index (- n 1)))
    ;; I don't introduce dynamic-extent here just because the compiler notes in
    ;; SBCL are a bit annoying and it is rarely effective.
    (declare (fixnum index))
    (labels ((visit (v)
               (when (= 0 (aref marked v))
                 (when (= 1 (aref tmp-marked v))
                   (error 'cycle-detected-error :graph graph :vertex v))
                 (setf (aref tmp-marked v) 1)
                 (dolist (next (aref graph v))
                   (visit next))
                 (setf (aref marked v) 1
                       (aref result index) v)
                 (decf index))))
      (dotimes (v n result)
        (when (= 0 (aref marked v))
          (visit v))))))

;;;
;;; Some operations on symmetric group
;;;

(defpackage :cp/symmetric-group
  (:use :cl)
  (:export #:decompose-to-cycles #:perm* #:perm-inverse #:make-identity-permutation))
(in-package :cp/symmetric-group)

;; NOTE: Here the underlying set is 0-based: {0, 1, 2, ..., N-1}

(declaim (inline decompose-to-cycles))
(defun decompose-to-cycles (permutation)
  "Returns the list of all the cyclic permutations in PERMUTATION and returns
its parity as the second value. (Actually the second value is the distance to
the identity permutation, (0, 1, ..., N-1), w.r.t. swapping.)"
  (declare (vector permutation))
  (let* ((n (length permutation))
         result
         (visited (make-array n :element-type 'bit :initial-element 0))
         (sign 0))
    (declare ((integer 0 #.most-positive-fixnum) sign))
    (dotimes (init n)
      (when (zerop (sbit visited init))
        (push (loop for x = init then (aref permutation x)
                    until (= (sbit visited x) 1)
                    collect x
                    do (setf (sbit visited x) 1)
                       (incf sign))
              result)
        (decf sign)))
    (values result sign)))

(declaim (inline perm*))
(defun perm* (perm1 perm2)
  "Composes two permutations. (Actually the arguments doesn't need to be
permutations. This is just a composition of two maps.)"
  (let* ((n (length perm1))
         (result (make-array n :element-type 'fixnum)))
    (dotimes (i n)
      (setf (aref result i) (aref perm2 (aref perm1 i))))
    result))

(declaim (inline perm-inverse))
(defun perm-inverse (perm)
  (let* ((n (length perm))
         (result (make-array n :element-type 'fixnum)))
    (dotimes (i n)
      (setf (aref result (aref perm i)) i))
    result))

(declaim (inline make-identity-permutation))
(defun make-identity-permutation (size)
  "Returns #(0 1 2 ... SIZE-1)."
  (declare ((integer 0 #.most-positive-fixnum) size))
  (let ((result (make-array size :element-type 'fixnum)))
    (dotimes (i size)
      (setf (aref result i) i))
    result))

(defpackage :cp/read-fixnum
  (:use :cl)
  (:export #:read-fixnum))
(in-package :cp/read-fixnum)

(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
  "NOTE: cannot read -2^62"
  (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 #\-))
                                  (setq 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))))))))

;; BEGIN_USE_PACKAGE
(eval-when (:compile-toplevel :load-toplevel :execute)
  (use-package :cp/read-fixnum :cl-user))
(eval-when (:compile-toplevel :load-toplevel :execute)
  (use-package :cp/symmetric-group :cl-user))
(eval-when (:compile-toplevel :load-toplevel :execute)
  (use-package :cp/topological-sort :cl-user))
(in-package :cl-user)

;;;
;;; Body
;;;

(defun main ()
  (let* ((n (read))
         (m (read))
         (graph (make-array n :element-type 'list :initial-element nil))
         (revgraph (make-array n :element-type 'list :initial-element nil)))
    (dotimes (i (+ n -1 m))
      (let ((a (- (read-fixnum) 1))
            (b (- (read-fixnum) 1)))
        (push b (aref graph a))
        (push a (aref revgraph b))))
    (let* ((vs (topological-sort graph))
           (invs (perm-inverse vs))
           (res (make-array n :element-type 'uint31 :initial-element 0)))
      #>revgraph
      (loop for v across vs
            for parents = (aref revgraph v)
            for true-parent = -1
            do (loop for p in parents
                     when (or (= true-parent -1)
                              (> (aref invs p) (aref invs true-parent)))
                     do (setq true-parent p))
               (setf (aref res v) (+ true-parent 1)))
      (write-string
       (with-output-to-string (*standard-output* nil :element-type 'base-char)
         (map () #'println res))))))

#-swank (main)

;;;
;;; Test and benchmark
;;;

#+swank
(defun get-clipbrd ()
  (with-output-to-string (out)
    #+os-windows (run-program "powershell.exe" '("-Command" "Get-Clipboard") :output out :search t)
    #+os-unix (run-program "xsel" '("-b" "-o") :output out :search t)))

#+swank (defparameter *this-pathname* (uiop:current-lisp-file-pathname))
#+swank (defparameter *dat-pathname* (uiop:merge-pathnames* "test.dat" *this-pathname*))

#+swank
(defun run (&optional thing (out *standard-output*))
  "THING := null | string | symbol | pathname

null: run #'MAIN using the text on clipboard as input.
string: run #'MAIN using the string as input.
symbol: alias of FIVEAM:RUN!.
pathname: run #'MAIN using the text file as input."
  (let* ((*standard-output* (or out (make-string-output-stream)))
         (res (etypecase thing
                (null
                 (with-input-from-string (*standard-input* (delete #\Return (get-clipbrd)))
                   (main)))
                (string
                 (with-input-from-string (*standard-input* (delete #\Return thing))
                   (main)))
                (symbol (5am:run! thing))
                (pathname
                 (with-open-file (*standard-input* thing)
                   (main))))))
    (if out res (get-output-stream-string *standard-output*))))

#+swank
(defun gen-dat ()
  (uiop:with-output-file (out *dat-pathname* :if-exists :supersede)
    (format out "")))

#+swank
(defun bench (&optional (out (make-broadcast-stream)))
  (time (run *dat-pathname* out)))

#-swank
(eval-when (:compile-toplevel)
  (when (and (boundp 'sb-c::*compiler-warning-count*)
             (> sb-c::*compiler-warning-count* 0))
    (sb-ext:quit :unix-status 1)))

;; To run: (5am:run! :sample)
#+swank
(it.bese.fiveam:test :sample
  (it.bese.fiveam:is
   (equal "0
1
2
"
          (run "3 1
1 2
1 3
2 3
" nil)))
  (it.bese.fiveam:is
   (equal "6
4
2
0
6
2
"
          (run "6 3
2 1
2 3
4 1
4 2
6 1
2 6
4 6
6 5
" nil))))


Measured memory_bytes: 47880