#P2169. Kingdom of Magic
Kingdom of Magic
描述
魔法王国自古以来就拥有一个连接各城市的双向魔法传送门网络。每个传送门通过魔法连接着一对城市,使得城市之间能够进行快速的魔法通讯和旅行。由魔法传送门连接的城市被称为相邻城市。 阿尔伯特王子和贝蒂公主住在相邻的城市。从他们小时候起,阿尔伯特和贝蒂就一直通过魔法通讯水晶球保持联系,而水晶球是通过城市之间的魔法传送门来工作的。 阿尔伯特和贝蒂彼此相爱。他们的爱如此深厚,以至于他们一分钟都不能没有对方。他们总是随身携带水晶球,这样他们就可以随时和对方交谈。他们的爱有些奇怪 —— 他们从未见过彼此,甚至害怕同时处于同一个城市。人们说,水晶球的魔法影响了他们。 对于阿尔伯特和贝蒂来说,在王国中旅行是一件复杂的事情。他们必须通过魔法传送门旅行,即使对于皇室家庭来说,这也有点昂贵。他们可以同时使用一对传送门移动到另一对不同的城市,或者他们中的一个使用传送门,而另一个留在原地。在他们旅行的任何时刻,他们都必须处于相邻的城市。他们不能同时通过同一个传送门移动。 编写一个程序来帮助阿尔伯特和贝蒂从一对城市旅行到另一对城市。程序必须找到最便宜的旅行计划 —— 即通过魔法传送门移动的次数最少。当他们同时通过传送门移动时,计为两次移动。
输入
输入的第一行包含整数 。这里是王国中的城市数量(城市从 到 编号);是魔法传送门的数量;分别是阿尔伯特和贝蒂开始旅行的相邻城市;分别是阿尔伯特和贝蒂想要到达的相邻城市( 或者 )。接下来的行描述传送门。每行包含两个数字 和 ()—— 由传送门连接的城市。最多只有一个传送门连接两个城市。
输出
在输出的第一行写入两个数字 和 。这里 是旅行计划中的最少移动次数;k 是阿尔伯特和贝蒂在旅行过程中访问的相邻城市对的数量,包括开始时的 、 和结束时的 、。 然后写入 行,每行有两个整数 和 —— 阿尔伯特和贝蒂在旅行过程中依次访问的不同的相邻城市对。如果有多个移动次数相同的旅行计划,则输出其中任意一个。保证存在解决方案。
输入数据 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