热带岛屿负责道路的人们想修理和升级岛上各个旅游景点之间的道路。道路本身也很有趣，它们从不在交叉路口汇合，而是通过桥梁和隧道相互交叉或相互通过。通过这种方式,每条道路都在两个特定的旅游景点之间运行，这样游客就不会迷失。不幸的是，当建筑公司在特定道路上工作时，该道路在任何一个方向都无法使用。如果在两个旅游景点之间无法通行，则即使建筑公司在任何特定时间只在一条道路上工作，也可能出现问题。道路部门已经决定在景点之间建造新的道路，以便在最终配置中，如果任何一条道路正在建设，则仍然可以使用剩余的道路在任意两个旅游景点之间旅行。我们的任务是找到所需的最少数量的新道路。

输入的第Ⅰ行将包括正整数n (3≤n≤1000）和r (2≤r≤1000)，其中n是旅游景点的数量，r是道路的数量。旅游景点的编号为1~n。以下r行中的每一行都将由两个整数v和w组成，表示在v和w的景点之间存在道路。道路是双向的，在任何两个旅游景点之间最多有一条道路。此外，在目前的配置中，可以在任意两个旅游景点之间旅行。

单行输出需要添加的最少道路数量。

本题有多组样例