15994번 - 엘리베이터 2 스페셜 저지

N층으로 이뤄진 고층 아파트에 M대의 엘리베이터가 있다. 각 엘리베이터에는 1부터 M까지 번호가 매겨져있다.

아파트 관리인은 유지비를 줄이기 위하여 각 엘리베이터가 특정한 층에서만 서도록 하였다. 그 결과 i번 엘리베이터는 X_i번째 층에서부터 시작하여 매 Y_i번째 층에서만 선다. 예를 들어 X_i = 4, Y_i = 3이라면 i번 엘리베이터는 4층, 7층, 10층, …에서만 서게 된다.

이 아파트 A층에서 사는 철수는 B층에 있는 친구 집에 놀러 가려고 한다. 그런데 가능하면 엘리베이터를 타는 횟수를 줄이고 싶어 한다.

예를 들어 아파트가 총 12층이고, 엘리베이터가 3대 있으며, 각 엘리베이터가 다음과 같이 운행한다고 하자.

10층에서 8층으로 가기 위해서는 1번 - 2번 - 3번 엘리베이터를 차례로 탈 수도 있고, 1번 - 3번 엘리베이터를 탈 수도 있다. 어떤 방법이든 최소 두 번 엘리베이터를 타야한다.

N과 M 그리고 엘리베이터 운행 정보가 주어질 때 철수가 최소 몇 번 엘리베이터를 타야하는지와 타야할 엘리베이터의 순서를 구하는 프로그램을 작성하시오.

첫째 줄에는 N과 M이 빈 칸을 사이에 두고 주어진다.

둘째 줄부터 M줄에 걸쳐 엘리베이터 번호 순서대로 X_i와 Y_i가 빈 칸을 사이에 두고 주어진다.

마지막 줄에는 A와 B가 주어진다. A와 B는 서로 다른 수임이 보장된다.

첫째 줄에는 A층에서 B층으로 가기 위해 최소 몇 번 엘리베이터를 타야하는지를 출력한다.

다음 줄부터 타야하는 엘리베이터의 번호를 한 줄에 하나씩 타는 순서대로 출력한다. 또한 엘리베이터를 타는 방법이 여러 가지인 경우에는 그 중의 한 방법만을 출력한다. 만약 A층에서 B층으로 갈 수 없다면 첫째 줄에 -1을 출력한다.

• 1 ≤ N ≤ 50,000,000
• 1 ≤ M ≤ 100
• 1 ≤ X_i, Y_i ≤ N
• A ≠ B