石老板生活的国家正在发生翻天覆地的变化。这个国家有 n 个城市，每两个城市都是由公路相互直接连通的。但是为了让普通居民出行方便，国王打算把 m 条公路改修为铁路，让居民可以乘坐火车出行。

要知道当火车和汽车同时到达同一所城市时是会发生车祸的，所以这样的情况是不被允许的。这里为了简化题目，假设火车和汽车的速度是相等的，每两个城市间的距离也是相等的。汽车和火车从一个城市到达另一城市需要的时间为 1。

石老板把所有的城市进行了编号，他在想如果有一辆火车和一辆汽车同时从 1 号城市出发到 n 号城市，所需要的最短时间是多少 ( 最短时间 = MAX ( 火车到达的时间，汽车到达的时间 ) ) ？

第一行输入一个整数 n (1<=n<=100) 和一个整数 m (1<=m<=1000)，分别表示这个国家的城市数量和改修公路数目。

接下来会有 m 行输入，每行有两个整数 x(1<=x<=n)和 y(1<=y<=n) 。表示把城市 x 和城市 y 连接的公路改修为铁路。