Kingdom of Magic#5159

Kingdom of Magic

1 secondo

64 megabyte

Difficile

Kingdom of Magic has had a network of bidirectional magic portals between cities since ancient times. Each portal connects a pair of cities and allows fast communication and travel between them. Cities that are connected by a magic portal are called neighboring.

Prince Albert and Princess Betty live in neighboring cities. Since their childhood, Albert and Betty have always been in touch using magic communication orbs, which work via a magic portal between the cities.

Albert and Betty are in love with each other. Their love is so great that they cannot live a minute without each other. They always carry the orbs with them, so they can talk to each other at any time.

There is something strange about their love: they have never seen each other, and they even fear being in the same city at the same time. People say that the magic of the orbs has affected them. Traveling through the Kingdom is a complicated affair for Albert and Betty. They have to travel through magic portals, which is somewhat expensive even for royal families. They can simultaneously use a pair of portals to move to a different pair of cities, or just one of them can use a portal while the other stays where they are. At any moment of their travel, they must be in neighboring cities. They cannot simultaneously move through the same portal.

Write a program that helps Albert and Betty travel from one pair of cities to another pair. It must find the cheapest travel plan — with the minimal number of times they have to move through the magic portals. When they move through the portals simultaneously, it counts as two moves.

Input

Input contains several datasets. The first line of each dataset contains integer numbers $n, m, a_{1}, b_{1}, a_{2}, b_{2}$ n, m, a_1, b_1, a_2, b_2. Here, $n$ ( $3 \leq n \leq 100$ 3 \leq n \leq 100) is the number of cities in the Kingdom (cities are numbered from $1$ to $n$ ); $m$ ( $2 \leq m \leq 1000$ 2 \leq m \leq 1000) is the number of magic portals; $a_{1}, b_{1}$ a_1, b_1 ( $1 \leq a_{1}, b_{1} \leq n$ 1 \leq a_1, b_1 \leq n, $a_{1} \neq = b_{1}$ a_1 \neq b_1) are the neighboring cities where Albert and Betty, respectively, start their travel; $a_{2}, b_{2}$ a_2, b_2 ( $1 \leq a_{2}, b_{2} \leq n$ 1 \leq a_2, b_2 \leq n, $a_{2} \neq = b_{2}$ a_2 \neq b_2) are the neighboring cities where Albert and Betty, respectively, want to arrive ( $a_{1} \neq = a_{2}$ a_1 \neq a_2 or $b_{1} \neq = b_{2}$ b_1 \neq b_2). The following $m$ lines describe the portals. Each line contains two numbers $p_{i 1}$ p_{i1} and $p_{i 2}$ p_{i2} ( $1 \leq p_{i 1}, p_{i 2} \leq n$ 1 \leq p_{i1}, p_{i2} \leq n, $p_{i 1} \neq = p_{i 2}$ p_{i1} \neq p_{i2}): the cities that are connected by the portal. There is at most one portal connecting any two cities.

Output

For each test case, output on the first line two numbers: $c$ and $k$ . Here, $c$ is the minimal number of moves in the travel plan; $k$ is the number of neighboring city pairs that Albert and Betty visit during their travel, including $a_{1}, b_{1}$ a_1, b_1 at the start and $a_{2}, b_{2}$ a_2, b_2 at the end. Then output $k$ lines with two integers $a_{i}^{'}$ a'_i and $b_{i}^{'}$ b'_i on each line – consecutive distinct pairs of neighboring cities that Albert and Betty visit during their travel. If there are multiple travel plans with the same number of moves, output any of them. It is guaranteed that a solution exists. Print a blank line between consecutive datasets.

Esempi

Esempio 1