;; -*- coding: utf-8 -*-
(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)) (read s nil nil t))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)
#-swank (disable-debugger) ; for CS Academy

;; BEGIN_INSERTED_CONTENTS
;;;
;;; Biconnected components, bridges, and block-cut tree of undirected graph
;;;

;; PAY ATTENTION TO THE STACK SIZE! MAKE-BCC does DFS.

(defstruct (bcc (:constructor %make-bcc (graph preorders components sizes count bridges)))
  ;; undirected graph (as a vector of adjacency lists)
  (graph nil :type vector)
  ;; preorders[i] := the ordinal number of the i-th vertex by pre-order DFS 
  (preorders nil :type (simple-array fixnum (*)))
  ;; components[i] := the biconnected component to which the i-th vertex of
  ;; GRAPH belongs
  (components nil :type (simple-array (integer 0 #.most-positive-fixnum) (*)))
  ;; sizes[k] := size of the k-th biconnected component
  (sizes nil :type (simple-array (integer 0 #.most-positive-fixnum) (*)))
  ;; the total number of biconnected components
  (count 0 :type (integer 0 #.most-positive-fixnum))
  ;; the list of bridges between two biconnected components (Each edge is stored
  ;; as a cons cell (vertex1 . vertex2), where vertex1 < vertex2 holds.)
  (bridges nil :type list))

(defun make-bcc (graph)
  "GRAPH := vector of adjacency lists

- This function doesn't check if GRAPH is really undirected.
- A multi-edge is regarded as a single edge."
  (declare (optimize (speed 3))
           (vector graph))
  (let* ((n (length graph))
         (preorders (make-array n :element-type 'fixnum :initial-element -1))
         (preord 0)
         (components (make-array n :element-type '(integer 0 #.most-positive-fixnum)))
         (bcc-ord 0) ; is always equal to the current number of the components
         (sizes (make-array n :element-type '(integer 0 #.most-positive-fixnum)))
         stack
         (in-stack (make-array n :element-type 'bit :initial-element 0))
         roots
         bridges)
    (declare ((integer 0 #.most-positive-fixnum) preord bcc-ord))
    (labels ((dfs (v prev)
               (declare (fixnum v prev))
               (setf (aref preorders v) preord)
               (incf preord)
               ;; push current vertex to stack
               (push v stack)
               (setf (aref in-stack v) 1)
               (push v roots)
               (dolist (neighbor (aref graph v))
                 (cond ((= -1 (aref preorders neighbor))
                        ;; not yet visited
                        (dfs neighbor v))
                       ((and (/= neighbor prev)
                             (= 1 (sbit in-stack neighbor)))
                        ;; When a backward edge to a not yet classified vertex
                        ;; exists, then these vertices comprise a biconnected
                        ;; component.
                        (loop while (> (aref preorders (car roots))
                                       (aref preorders neighbor))
                              do (pop roots)))))
               ;; add a new component
               (when (= v (the fixnum (car roots)))
                 (unless (= prev -1)
                   (push (if (<= prev v) (cons prev v) (cons v prev))
                         bridges))
                 (let ((size 0)) ; size of the component
                   (declare ((integer 0 #.most-positive-fixnum) size))
                   (loop
                     (let ((node (pop stack)))
                       (setf (aref components node) bcc-ord)
                       (setf (sbit in-stack node) 0)
                       (incf size)
                       (when (= node v)
                         (return))))
                   (setf (aref sizes bcc-ord) size)
                   (incf bcc-ord)
                   (pop roots)))))
      (dotimes (v n)
        (when (= -1 (aref preorders v))
          (dfs v -1)))
      (%make-bcc graph preorders components sizes bcc-ord bridges))))

(declaim (ftype (function * (values (simple-array t (*)) &optional)) make-block-cut))
(defun make-block-cut (bcc)
  "Makes a block-cut tree (or forest, if not connected). Returns the vector of
adjacency lists."
  (declare (optimize (speed 3)))
  (let* ((graph (bcc-graph bcc))
         (n (length graph))
         (comp-n (bcc-count bcc))
         (components (bcc-components bcc))
         (tree (make-array comp-n :element-type t)))
    (dotimes (i comp-n)
      (setf (aref tree i) (make-hash-table :test #'eql)))
    (dotimes (i n)
      (let ((i-comp (aref components i)))
        (dolist (neighbor (aref graph i))
          (let ((neighbor-comp (aref components neighbor)))
            (unless (= i-comp neighbor-comp)
              (setf (gethash neighbor-comp (aref tree i-comp)) t))))))
    (dotimes (i comp-n)
      (setf (aref tree i)
            (loop for x being each hash-key of (aref tree i) collect x)))
    tree))

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

(defun main ()
  (let* ((n (read))
         (m (read))
         (graph (make-array n :element-type 'list :initial-element nil)))
    (dotimes (i m)
      (let ((a (- (read) 1))
            (b (- (read) 1)))
        (push a (aref graph b))
        (push b (aref graph a))))
    (let ((bcc (make-bcc graph)))
      (println (length (bcc-bridges bcc))))))

#-swank (main)


;; For Test
#+swank
(defun io-equal (in-string out-string &key (function #'main) (test #'equal))
  "Passes IN-STRING to *STANDARD-INPUT*, executes FUNCTION, and returns true if
the string output to *STANDARD-OUTPUT* is equal to OUT-STRING."
  (labels ((ensure-last-lf (s)
             (if (eql (uiop:last-char s) #\Linefeed)
                 s
                 (uiop:strcat s uiop:+lf+))))
    (funcall test
             (ensure-last-lf out-string)
             (with-output-to-string (out)
               (let ((*standard-output* out))
                 (with-input-from-string (*standard-input* (ensure-last-lf in-string))
                   (funcall function)))))))

#+swank
(defun get-clipbrd ()
  (with-output-to-string (out)
    (run-program "C:/msys64/usr/bin/cat.exe" '("/dev/clipboard") :output out)))

#+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* out))
    (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))))))

#+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)))

;; To run: (5am:run! :sample)
#+swank
(it.bese.fiveam:test :sample
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7
"
    "4
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "3 3
1 2
1 3
2 3
"
    "0
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "6 5
1 2
2 3
3 4
4 5
5 6
"
    "5
")))


Measured memory_bytes: 29796