2401: 魔法王国

从古代开始，魔法王国就有一个由双向魔法门构成的网络。每一个魔法门以魔法连接一对城市，允许他们进行魔法交流和旅行。被魔法门连接起来的城市被称为相邻的。

Albert王子和Betty公主住在相邻的城市。所以，在他们的孩提时代，Albert和Betty经常通过魔法通讯球保持联系，魔法通讯球是通过连接城市的魔法门工作的。

Albert和Betty相爱了。他们爱得如此深以至不能在没有对方时生活一分钟。他们总是把魔法球带在身边，从而，他们可以在任何时候与对方说话。他们的爱情有一个奇怪的事情——他们从没见过对方，甚至他们害怕同时在同一个城市。人们说，是魔法球影响了他们。

对于Albert和Betty来说，在王国里旅行是一件复杂的事情。他们必须通过魔法门旅行，这对于皇家而言也是非常昂贵的。他们可以同时使用不同的魔法门移动到不同的城市，也可以一方使用魔法门移动到一个城市，另一方呆在一个城市。在任何时候他们必须在相邻的城市。他们不能同时使用同一个魔法门移动。

写一个程序来帮助Albert和Betty从一对城市到另外一对城市。必须找到一个最便宜的方案——他们通过魔法门移动的次数最少。如果他们同时使用魔法门，计做两次移动。

输入文件的第一行包含整数n，m，a₁，b₁，a₂，b₂。这里n（3 <= n <=100）是王国里的城市数（城市从1到n标号）；m（2 <= m <= 1000）是魔法门的个数；a₁，b₁(1<=a₁，b₁<=n,a₁≠b₁)是相邻的城市，对应的分别是Albert和Betty的出发城市；a₂，b₂(1<=a₂，b₂<=n,a₂≠b₂)也是相邻的城市，对应的分别是Albert和Betty希望到达的城市。

接下来的m行描述魔法门。每一行包含两个数p_i1和p_i2(1<=p_i1，p_i2<=n,p_i1≠p_i2)——用魔法门相连的城市。任意两个城市之间最多只有一个魔法门连接。

输出文件一行包含一个整数c。这里c是方案中最少的移动次数。

4 5 1 2 2 1
1 2
2 3
3 4
4 1
1 3

3