Problem K. Kingdom of Magic ≡

Statement

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

Prince Albert and Princess Betty are living in the neighboring cities. Since their childhood Albert and Betty were always in touch with each other 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 that 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 to be in the same city at the same time. People say that the magic of the Orbs have 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 the portals to move to a different pair of cities, or just one of them can use a portal, while the other one stays where he or she is. At any moment of their travel they have to be in a neighboring cities. They cannot simultaneously move through the same portal.

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

Input file format

The first line of the input file contains integer numbers n, m, a₁, b₁, a₂, b₂. Here n is a number of cities in the Kingdom (cities are numbered from 1 to n); m is a number of magic portals; a₁, b₁ (1 ≤ a₁, b₁ ≤ n, a₁ <> b₁) are the neighboring cities where Albert and Betty correspondingly start their travel from; a₂, b₂ (1 ≤ a₂, b₂ ≤ n, a₂ <> b₂) are the neighboring cities where Albert and Betty correspondingly want to get to (a₁ <> a₂ or b₁ <> b₂).

Following m lines describe the portals. Each line contains two numbers p_i1 and p_i2 (1 ≤ p_i1, p_i2 ≤ n, p_i1 <> p_i2) — cities that are connected by the portal. There is at most one portal connecting two cities.

Output file format

On the first line of the output file write 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₁, b₁ at the start and a₂, b₂ at the end.

Then write k lines with two integer numbers a'_i and b'_i on each line — consecutive different pairs of neighboring cities that Albert and Betty visit during their travel. If there are multiple travel plans with the same number of moves, then write any of them. It is guaranteed that solution exists.

Constraints

Sample tests

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

3 3
1 2
2 3
2 1