Makima's Lunch Pick for Today

Interview

Time limit1sMemory limit1024 MB

Summary

Find the restaurant that Power, Denji, and Aki can each reach by walks of the same length over one-way roads, minimizing that length, and print their walks.

Level: Medium6 of 10
Topics: Graph, BFS, Dynamic programming
Solved: No attempts yet

Problem

Power, Denji, and Aki agreed to eat lunch together. But they misread the restaurant name, and the three of them ended up at different restaurants!

~~Three people~~ A devil, a chainsaw man, and a human each insisted that the others come to the restaurant where they were. In the end they agreed to pick one restaurant in between and meet there. So which restaurant should it be?

The restaurants are connected by one-way roads, and every road has the same length.

Nobody wanted to walk more than the others, so the three of them agreed to start from the $3$ restaurants where they are and find a restaurant they can each reach by walking routes of the same length.

They are fools, so they do not notice when a route passes the same road several times. Since every road has the same length, the length of a route is the total number of times it crosses roads.

Makima, who has a kind heart, wants to find a restaurant where the three can meet. Help Makima find one. Lunchtime keeps passing while they walk, so find the restaurant with the shortest route length, so the three can eat as soon as possible.

Input

The first line contains the integers $N$ , the number of restaurants, and $M$ , the number of roads. ( $4 \leq N \leq 44$ , $1 \leq M \leq 888$ )

The second line contains $A$ , $B$ , and $C$ , the numbers of the restaurants where Power, Denji, and Aki are. ( $1 \leq A, B, C \leq N$ , $A \neq B, B \neq C, A \neq C$ )

The next $M$ lines each contain $s$ and $e$ , the start and end restaurants of a road. ( $1 \leq s, e \leq N$ , $s \neq e$ )

No road with the same $s$ and $e$ is given more than once.

Output

If Power, Denji, and Aki cannot meet, print -1 on the first line.

Otherwise, print the number of the meeting restaurant and the length of the route they must walk on the first line. Then print, on each of the next $3$ lines, the restaurants on the route that Power, Denji, and Aki must walk, in order.

Examples3

Example 1
Input
```
4 3
1 2 3
1 4
2 4
3 4
```
Expected output
```
4 1
1 4
2 4
3 4
```
Example 2
Input
```
4 3
1 2 3
4 1
4 2
4 3
```
Expected output
```
-1
```

Example 3

Input

Expected output

1 6
1 2 3 1 2 3 1
2 3 1 2 3 4 1
3 4 1 2 3 4 1