在一个叫奥斯汀的城市，有 n 个小镇（从 1 到 n 编号），这些小镇通过 m 条双向火车铁轨相连。当然某些小镇之间也有公路相连。为了保证每两个小镇之间的人可以方便的相互访问，市长就在那些没有铁轨直接相连的小镇之间建造了公路。在两个直接通过公路或者铁路相连的小镇之间移动，要花费一个小时的时间。
现在有一辆火车和一辆汽车同时从小镇 1 出发。他们都要前往小镇 n，但是他们中途不能同时停在同一个小镇（但是可以同时停在小镇 n）。火车只能走铁路，汽车只能走公路。
现在请来为火车和汽车分别设计一条线路；所有的公路或者铁路可以被多次使用。使得火车和汽车尽可能快的到达小镇 n。即要求他们中最后到达小镇 n 的时间要最短。输出这个最短时间。（最后火车和汽车可以同时到达小镇 n，也可以先后到达。）
单组测试数据。
第一行有两个整数 n 和 m (2 <= n <= 400, 0 <= m <= n*(n-1)/2)，表示小镇的数目和铁轨的数目。
接下来 m 行，每行有两个整数 u 和 v，表示 u 和 v 之间有一条铁路。(1 <= u, v <= n, u != v)。
输入中保证两个小镇之间最多有一条铁路直接相连。
输出一个整数，表示答案，如果没有合法的路线规划，输出 -1。
没有铁路直接相连的两个小镇之间一定有一条公路，所以公路图就是铁路图的补图。
小镇 1 到小镇 n 之间要么有铁路、要么有公路，也就是说两种交通方式中必有一种可以一步到达终点。因此不存在两者同时停靠在同一个中间小镇的情况，直接分别求铁路图和公路图上 1 到 n 的最短路，答案就是两者的较大值。
若其中一种方式无法从 1 到达 n，则输出 -1。由于 n <= 400，用 BFS 即可，复杂度 O(n^2)。