module mod_union_find
  implicit none
  type union_find
    integer :: n = 0
    integer, allocatable :: par(:), rnk(:), cnt(:)
  contains
    procedure :: find => find
    procedure :: same => same
    procedure :: unite => unite
    procedure :: size => size_of
  end type
  interface union_find
    module procedure :: newuf
  end interface
contains
  type(union_find) function newuf(n) result(res)
    integer, intent(in) :: n
    integer :: i
    res%n = n
    allocate(res%par(n), res%rnk(n), res%cnt(n))
    res%par = [(i, i = 1, n)]
    res%rnk = 0
    res%cnt = 1
  end
  recursive integer function find(this, i) result(res)
    class(union_find), intent(inout) :: this
    integer, intent(in) :: i
    if (this%par(i) /= i) this%par(i) = find(this, this%par(i))
    res = this%par(i)
  end
  logical function same(this, i, j) result(res)
    class(union_find), intent(inout) :: this
    integer, intent(in) :: i, j
    res = find(this, i) == find(this, j)
  end
  subroutine unite(this, i, j)
    class(union_find), intent(inout) :: this
    integer, intent(in) :: i, j
    integer :: x, y
    x = find(this, i)
    y = find(this, j)
    if (x == y) return
    if (this%rnk(x) < this%rnk(y)) then
      this%par(x) = y
      this%cnt(y) = this%cnt(y) + this%cnt(x)
    else
      this%par(y) = x
      this%cnt(x) = this%cnt(x) + this%cnt(y)
      if (this%rnk(x) == this%rnk(y)) this%rnk(x) = this%rnk(x) + 1
    end if
  end
  integer function size_of(this, i) result(res)
    class(union_find), intent(inout) :: this
    integer, intent(in) :: i
    res = this%cnt(find(this, i))
  end
end module mod_union_find
program connect_cities
  use mod_union_find
  implicit none
  integer :: n, m, a, b, i
  type(union_find) :: uf
  read(*,*) n, m
  uf = union_find(n)
  do i = 1, m
    read(*,*) a, b
    if (uf%same(a, b)) cycle
    call uf%unite(a, b)
    n = n - 1
  end do
  write(*,'(i0)') n - 1
end program connect_cities