시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 245 89 57 36.306%

문제

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

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

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

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

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

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

입력

첫째 줄에는 N과 M이 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 M줄에 걸쳐 엘리베이터 번호 순서대로 Xi와 Yi가 빈 칸을 사이에 두고 주어지며, 마지막 줄에는 A와 B가 주어진다. N은 100,000이하, M은 100이하의 자연수이며, Xi, Yi, A, B는 모두 N이하의 자연수이다.

출력

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

예제 입력

12 3
4 3
7 5
4 4
10 8

예제 출력

2
1
3

힌트