#|
------------------------------------
                Utils                
------------------------------------
|#

(in-package :cl-user)

(defconstant +mod+ 1000000007)
;(defconstant +mod+ 998244353)

(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (progn (ql:quickload '(:cl-debug-print :fiveam))
                 (shadow :run)
                 (use-package :fiveam)))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)

#-swank
(unless (member :child-sbcl *features*)
  (quit
   :unix-status
   (process-exit-code
    (run-program *runtime-pathname*
                 `("--control-stack-size" "128MB"
                   "--noinform" "--disable-ldb" "--lose-on-corruption" "--end-runtime-options"
                   "--eval" "(push :child-sbcl *features*)"
                   "--script" ,(namestring *load-pathname*))
                 :output t :error t :input t))))




(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~a" b)) () '(signed-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~a" b)) () '(unsigned-byte ,b))) bits)))

(define-int-types 2 4 8 16 32 64)

(defmacro buffered-read-line (&optional (buffer-size 30) (in '*standard-input*) (term-char #\Space))
  (let ((buffer (gensym))
        (character (gensym))
        (idx (gensym)))
    `(let* ((,buffer (load-time-value (make-string ,buffer-size :element-type 'base-char))))
       (declare (simple-base-string ,buffer)
                (inline read-byte))
       (loop for ,character of-type base-char =
                ,(if (member :swank *features*)
                     `(read-char ,in nil #\Newline) ; on SLIME
                     `(code-char (read-byte ,in nil #.(char-code #\Newline))))
             for ,idx from 0
             until (char= ,character #\Newline)
             do (setf (schar ,buffer ,idx) ,character)
             finally (when (< ,idx ,buffer-size)
                       (setf (schar ,buffer ,idx) ,term-char))
                     (return (values ,buffer ,idx))))))

(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
  (declare (inline read-byte)
           #-swank (sb-kernel:ansi-stream in))
  (macrolet ((%read-byte ()
               `(the (unsigned-byte 8)
                     #+swank (char-code (read-char in nil #\Nul))
                     #-swank (read-byte in nil 0))))
    (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) (the (integer 0 #.(floor most-positive-fixnum 10)) (* result 10))))
              (return (if minus (- result) result))))))))


(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1
        (write obj :stream stream)
      (fresh-line stream))))

(defmacro safe-sort (list test &key (key #'identity))
  `(progn
    (declaim (inline sort sb-impl::stable-sort-list))
    (sort (copy-seq ,list) ,test :key ,key)))

(declaim (inline read-numbers-to-list))
(defun read-numbers-to-list (size)
  (loop repeat size collect (read-fixnum)))

(declaim (inline read-numbers-to-array))
(defun read-numbers-to-array (size)
  (let ((arr (make-array size
                         :element-type 'fixnum
                         :adjustable nil)))
    (declare ((array fixnum 1) arr))
    (loop for i of-type fixnum below size do
         (setf (aref arr i) (read-fixnum))
       finally
         (return arr))))

(defmacro read-characters-to-board (row-size column-size)
  (let ((board (gensym))
        (r (gensym))
        (c (gensym))
        (tmp (gensym)))
    `(let ((,board (make-array '(,row-size ,column-size) :element-type 'character :adjustable nil)))
       (dotimes (,r ,row-size ,board)
         (let ((,tmp (buffered-read-line)))
           (dotimes (,c ,column-size)
             (setf (aref ,board ,r ,c) (char ,tmp ,c))))))))

(declaim (inline princ-for-each-line))
(defmethod princ-for-each-line ((sequence list))
  (format t "~{~a~&~}" sequence))

(defmethod princ-for-each-line ((sequence vector))
  (loop for i below (length sequence) do
       (princ (aref sequence i))
       (fresh-line)))

(declaim (inline unwrap))
(defun unwrap (list)
  (the string
       (format nil "~{~a~^ ~}" list)))

(defmacro with-buffered-stdout (&body body)
  (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)))))

(defmacro maxf (place cand)
  `(setf ,place (max ,place ,cand)))

(defmacro minf (place cand)
  `(setf ,place (min ,place ,cand)))

(defmacro modf (place &optional (m +mod+))
  `(setf ,place (mod ,place ,m)))

(defmacro alambda (parms &body body)
  `(labels ((self ,parms ,@body))
     #'self))

(declaim (inline iota))
(defun iota (count &optional (start 0) (step 1))
  (loop for i from 0 below count collect (+ start (* i step))))

(declaim (inline int->lst))
(defun int->lst (integer)
  (declare ((integer 0) integer))
  (labels ((sub (int &optional (acc nil))
             (declare ((integer 0) int)
                      (list acc))
             (if (zerop int)
                 acc
                 (sub (floor int 10) (cons (rem int 10) acc)))))
    (sub integer)))

(declaim (inline lst->int))
(defun lst->int (list)
  (declare (list list))
  (labels ((sub (xs &optional (acc 0))
             (declare (ftype (function (list &optional (integer 0)) (integer 0)) sub))
             (declare (list xs)
                      ((integer 0) acc))
             (if (null xs)
                 acc
                 (sub (rest xs) (+ (* acc 10)
                                   (rem (first xs) 10))))))
    (the fixnum
         (sub list))))

(defun int->str (integer)
  (format nil "~a" integer))

(defun str->int (str)
  (parse-integer str))

(defun char->int (char)
  (declare (character char))
  (- (char-code char) #.(char-code #\0)))

(declaim (inline prime-factorize-to-list))
(defun prime-factorize-to-list (integer)
  (declare ((integer 0) integer))
  (the list
       (if (<= integer 1)
           nil
           (loop
              while (<= (* f f) integer)
              with acc list = nil
              with f integer = 2
              do
                (if (zerop (rem integer f))
                    (progn
                      (push f acc)
                      (setq integer (floor integer f)))
                    (incf f))
              finally
                (when (/= integer 1)
                  (push integer acc))
                (return (reverse acc))))))

(declaim (inline prime-p))
(defun prime-p (integer)
  (declare ((integer 1) integer))
  (if (= integer 1)
      nil
      (loop
         with f = 2
         while (<= (* f f) integer)
         do
           (when (zerop (rem integer f))
             (return nil))
           (incf f)
         finally
           (return t))))

(declaim (inline count-subsequence))
(defun count-subsequence (mainstr substr)
  (let ((main-len (length mainstr))
        (sub-len (length substr)))
    (count-if (lambda (i)
                (every (lambda (j)
                         (char-equal (char mainstr (+ i j))
                                     (char substr j)))
                       (iota sub-len)))
              (iota (1+ (- main-len sub-len))))))

(defmacro def-memoized-function (name lambda-list &body body)
  (let ((cache (gensym))
        (val (gensym))
        (win (gensym)))
    `(let ((,cache (make-hash-table :test #'equal)))
       (defun ,name ,lambda-list
         (multiple-value-bind (,val ,win) (gethash (list ,@lambda-list) ,cache)
           (if ,win
               ,val
               (setf (gethash (list ,@lambda-list) ,cache)
                     (progn
                       ,@body))))))))

#|
------------------------------------
                Body                
------------------------------------
|#

(in-package :cl-user)


(defclass uf-tree ()
  ((parents
    :initarg :parents
    :accessor parents)
   (group-count
    :initarg :group-count
    :accessor group-count)))


(defun uf-create (size)
  (declare (fixnum size))
  (make-instance 'uf-tree
                 :parents (make-array size :initial-element -1)
                 :group-count size))

(defmethod uf-find ((uf uf-tree) (x fixnum))
  (if (minusp (aref (parents uf) x))
      x
      (setf (aref (parents uf) x)
            (uf-find uf (aref (parents uf) x)))))

(defmethod uf-show-parents ((uf uf-tree))
  (map 'vector
       (lambda (x)
         (if (minusp x)
             x
             (uf-find uf x)))
       (parents uf)))
  

(defmethod uf-unite ((uf uf-tree) (x fixnum) (y fixnum))
  (when (> x y)
    (rotatef x y))
  (let ((x-parent (uf-find uf x))
        (y-parent (uf-find uf y)))
    (unless (= x-parent y-parent)
      (incf (aref (parents uf) x-parent)
            (aref (parents uf) y-parent))
      (setf (aref (parents uf) y-parent) x-parent)
      (decf (group-count uf)))))

(defmethod uf-get-tree-size ((uf uf-tree) (x fixnum))
  (- (aref (parents uf) (uf-find uf x))))


(defmethod uf-count-trees ((uf uf-tree))
  (group-count uf))

(defmethod uf-friends-p ((uf uf-tree) (x fixnum) (y fixnum))
  (= (uf-find uf x)
     (uf-find uf y)))


(defun main ()
  (declare #.OPT)
  (let* ((n (read))
         (m (read))
         (uf (uf-create n)))
    (declare (fixnum n m)
             (uf-tree uf))
    (dotimes (_ m)
      (let ((a (1- (read-fixnum)))
            (b (1- (read-fixnum))))
        (declare (fixnum a b))
        (uf-unite uf a b)))
    (princ (1- (uf-count-trees uf)))
    (fresh-line)))

#-swank (main)


Measured memory_bytes: 29172