There are N cities numbered 1 through N, and M bidirectional roads numbered 1 through M. Road i connects City A_i and City B_i.

Snuke can perform the following operation zero or more times:

* Choose two distinct cities that are not directly connected by a road, and build a new road between the two cities.



After he finishes the operations, it must be possible to travel from any city to any other cities by following roads (possibly multiple times).

What is the minimum number of roads he must build to achieve the goal?

Constraints

* 2 \leq N \leq 100,000
* 1 \leq M \leq 100,000
* 1 \leq A_i < B_i \leq N
* No two roads connect the same pair of cities.
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N M
A_1 B_1
:
A_M B_M


Output

Print the answer.

Example

Input

3 1
1 2


Output

1
import java.math.*;
import java.util.*;
import java.util.function.*;
import java.util.stream.*;

public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    List<UnionFind<Integer>> list = new ArrayList<>();
    for (int i = 0; i < n; i++) {
      list.add(new UnionFind<>(i));
    }
    for (int i = 0; i < m; i++) {
      int a = sc.nextInt() - 1;
      int b = sc.nextInt() - 1;
      UnionFind.union(list.get(a), list.get(b), Math::min);
    }
    Set<Integer> set = list.stream().map(UnionFind::getGroupValue).collect(Collectors.toSet());
    System.out.println(set.size() - 1);
  }
}

/**
 * Union Find
 * @param <T> 値の型
 */
class UnionFind<T> {
  /** 親 (なければnull) */
  private UnionFind<T> parent;
  /** 値 */
  private final T value;
  /** 所属するグループの合算した値 (root要素以外のgroupValueは正しいとは限らない) */
  private T groupValue;

  /**
   * Union Find
   * @param value 値
   */
  public UnionFind(T value) {
    this.value = value;
    this.groupValue = value;
  }

  /**
   * 同じグループに属するかどうか
   * @param a a
   * @param b b
   * @param <S> 値の型
   * @return 同じグループに属するならtrue
   */
  public static <S> boolean sameGroup(UnionFind<S> a, UnionFind<S> b) {
    return a.getRoot().equals(b.getRoot());
  }

  /**
   * 同じ木に所属させる
   * @param a a
   * @param b b
   * @param <S> 値の型
   */
  public static <S> void union(UnionFind<S> a, UnionFind<S> b) {
    union(a, b, (_1, _2) -> _1);
  }
  /**
   * 同じ木に所属させる。また、値の計算もする
   * @param a a
   * @param b b
   * @param groupValueFunction aとbが異なるグループに属するとき、その2つのグループの値を合算する関数。
   * @param <S> 値の型
   */
  public static <S> void union(UnionFind<S> a, UnionFind<S> b, BiFunction<S, S, S> groupValueFunction) {
    UnionFind<S> aRoot = a.getRoot();
    UnionFind<S> bRoot = b.getRoot();
    if (!aRoot.equals(bRoot)) {
      bRoot.parent = aRoot;
      aRoot.groupValue = groupValueFunction.apply(aRoot.groupValue, bRoot.groupValue);
    }
  }

  @Override
  public boolean equals(Object o) {
    return this == o;
  }

  /**
   * root要素を返す。
   * @return root要素
   */
  private UnionFind<T> getRoot() {
    if (parent == null) {
      return this;
    }
    UnionFind<T> root = parent.getRoot();
    parent = root;
    return root;
  }

  /**
   * この要素の値を返す。
   * @return 値
   */
  public T getValue() {
    return value;
  }

  /**
   * この要素が属するグループの値を返す。
   * @return グループの値
   */
  public T getGroupValue() {
    return getRoot().groupValue;
  }
}

