Background

Special for beginners, ^_^

Description

给定一个有$n$个点的无向完全图，其中所有有$m$条权值为$1$的边，其余的边均为$0$，问该完全图的最小生成树的费用为多少。

Format

Input

第一行给定两个整数分别为$n$，$m$，分别代表完全图中有$n$个点，有$m$条权值为$1$的边 后面输入有$m$行，每行两个值$u$，$v$代表从$u$到$v$有一条权值为$1$的边

Output

最小生成树的费用

Samples

2 0

0

3 2
1 2
1 3

1

Limitation

1s, 1024KiB for each test case.

for all case $1 \le n \le 10^5$, $1 \le m \le \min(10^5, \frac{(n-1)n}{2})$