#P2169. Kingdom of Magic

Kingdom of Magic

描述

魔法王国自古以来就拥有一个连接各城市的双向魔法传送门网络。每个传送门通过魔法连接着一对城市,使得城市之间能够进行快速的魔法通讯和旅行。由魔法传送门连接的城市被称为相邻城市。 阿尔伯特王子和贝蒂公主住在相邻的城市。从他们小时候起,阿尔伯特和贝蒂就一直通过魔法通讯水晶球保持联系,而水晶球是通过城市之间的魔法传送门来工作的。 阿尔伯特和贝蒂彼此相爱。他们的爱如此深厚,以至于他们一分钟都不能没有对方。他们总是随身携带水晶球,这样他们就可以随时和对方交谈。他们的爱有些奇怪 —— 他们从未见过彼此,甚至害怕同时处于同一个城市。人们说,水晶球的魔法影响了他们。 对于阿尔伯特和贝蒂来说,在王国中旅行是一件复杂的事情。他们必须通过魔法传送门旅行,即使对于皇室家庭来说,这也有点昂贵。他们可以同时使用一对传送门移动到另一对不同的城市,或者他们中的一个使用传送门,而另一个留在原地。在他们旅行的任何时刻,他们都必须处于相邻的城市。他们不能同时通过同一个传送门移动。 编写一个程序来帮助阿尔伯特和贝蒂从一对城市旅行到另一对城市。程序必须找到最便宜的旅行计划 —— 即通过魔法传送门移动的次数最少。当他们同时通过传送门移动时,计为两次移动。

输入

输入的第一行包含整数 nma1b1a2b2n、m、a1、b1、a2、b2。这里n3<=n<=100 n(3 <= n <= 100)是王国中的城市数量(城市从 11 nn 编号);m2<=m<=1000m(2 <= m <= 1000)是魔法传送门的数量;a1b11<=a1,b1<=na1!=b1a1、b1(1 <= a1, b1 <= n,a1 != b1)分别是阿尔伯特和贝蒂开始旅行的相邻城市;a2b21<=a2,b2<=na2!=b2a2、b2(1 <= a2, b2 <= n,a2 != b2)分别是阿尔伯特和贝蒂想要到达的相邻城市(a1!=a2a1 != a2 或者 b1!=b2b1 != b2)。接下来的m m 行描述传送门。每行包含两个数字 pi1p_{i1}pi2p_{i2}1<=pi1,pi2<=npi1!=pi21 <= p_{i1}, p_{i2} <= n,p_{i1} != p_{i2})—— 由传送门连接的城市。最多只有一个传送门连接两个城市。

输出

在输出的第一行写入两个数字 cckk。这里 cc 是旅行计划中的最少移动次数;k 是阿尔伯特和贝蒂在旅行过程中访问的相邻城市对的数量,包括开始时的 a1a_1b1b_1 和结束时的 a2a_2b2b_2。 然后写入 kk行,每行有两个整数 a0ia_{0i}b0ib_{0i}—— 阿尔伯特和贝蒂在旅行过程中依次访问的不同的相邻城市对。如果有多个移动次数相同的旅行计划,则输出其中任意一个。保证存在解决方案。

输入数据 1

4 5 1 2 2 1

1 2

2 3

3 4

4 1

1 3

输出数据 1

3 3

1 2

2 3

2 1