27451번 - 마키마씨가 정해주는 오늘 점심의 맛 스페셜 저지

파워와 덴지, 아키는 점심을 함께 먹기로 약속했다. 하지만 식당 이름을 착각하는 바람에 셋은 서로 다른 식당에 도착하고 말았다!

세 사람 마인 하나, 무기인간 하나, 사람 하나는 서로 자신이 있는 식당으로 오라며 다투었고, 결국 중간에 있는 식당 하나를 정해 그 식당에서 다시 모이기로 했다. 그런데, 어떤 식당으로 모이면 좋을까?

식당들은 일방통행 도로들로 연결되어 있으며, 모든 도로의 길이는 서로 같다.

누구도 다른 사람보다 많이 이동하고 싶어 하지 않았기 때문에, 약속 장소를 두고 싸우던 셋은 결국 이들이 있는 $3$ 개의 식당 각각에서 출발해서, 같은 길이의 경로로 이동해서 도착할 수 있는 식당을 찾기로 했다. 셋은 바보라서, 이동하는 경로에서 같은 도로를 여러 번 지나가도 알아차리지 못한다. 이때, 모든 도로의 길이는 같기 때문에 경로의 길이는 경로에 포함된 각 도로를 지나는 횟수의 합으로 정의한다.

마음씨가 착한 마키마 씨는 이들을 위해 셋이 만날 수 있는 식당을 찾아주려고 한다. 마키마 씨를 도와 셋이 만날 수 있는 식당을 찾아주자. 이동하는 동안 점심시간은 계속 지나기 때문에, 셋이 최대한 빨리 식사를 할 수 있게 이동하는 경로의 길이가 가장 짧은 식당을 찾아주자.

첫째 줄에는 정수인 식당의 개수 $N$과 도로의 개수 $M$이 주어진다. ($4 \leq N \leq 44$, $1 \leq M \leq 888$)

둘째 줄에는 파워, 덴지, 아키가 있는 식당의 번호인 $A$, $B$, $C$가 주어진다. ($1 \leq A, B, C \leq N$, $A \neq B, B \neq C, A \neq C$)

그다음 $M$줄에 걸쳐, 각 줄에 도로의 출발 식당 $s$, 도착 식당 $e$가 주어진다. ($1 \leq s, e \leq N$, $s \neq e$)

$s$와 $e$가 모두 같은 도로는 중복해서 주어지지 않는다.

파워와 덴지, 아키가 만날 수 있는 식당이 존재하지 않으면 첫째 줄에 -1을 출력한다.

그러한 식당이 존재한다면, 첫째 줄에 약속 장소로 정할 식당의 번호와 이동해야 하는 경로의 길이를 출력한다. 이후 $3$개의 줄에 각각 파워, 덴지와 아키가 이동해야 하는 경로에 있는 식당들을 순서대로 출력한다.