엘리베이터
시간 제한1초메모리 제한128 MB
등차수열 형태로 정지하는 엘리베이터들을 이용해 A층에서 B층까지 가는 최소 탑승 횟수와 경로를 구하는 문제입니다.
문제
N층짜리 고층 아파트에 M대의 엘리베이터가 있다. 엘리베이터에는 1번부터 M번까지 번호가 붙어 있다.
관리비를 줄이기 위해 각 엘리베이터는 정해진 층에서만 멈춘다. i번 엘리베이터는 Xi층에서 처음 멈추고, 그 뒤로 Yi층마다 멈춘다. 예를 들어 Xi = 4, Yi = 3이면 4층, 7층, 10층, ... 에서 멈춘다.
A층에 사는 철수는 B층에 있는 친구의 집에 가려고 한다. 철수는 가능한 한 엘리베이터를 적게 타고 싶다.
다음 그림처럼 아파트가 12층이고 엘리베이터가 3대 있다고 하자.
10층에서 8층으로 가려면 1번, 2번, 3번 엘리베이터를 차례로 탈 수도 있고, 1번과 3번 엘리베이터만 탈 수도 있다. 이 경우 엘리베이터를 최소 2번 타야 한다.
N, M, 각 엘리베이터의 운행 정보가 주어질 때, A층에서 B층으로 가기 위해 엘리베이터를 최소 몇 번 타야 하는지와 그때 타는 엘리베이터의 순서를 구하라.
입력
첫째 줄에 N과 M이 공백으로 구분되어 주어진다.
다음 M개의 줄에는 엘리베이터 번호 순서대로 Xi와 Yi가 공백으로 구분되어 주어진다.
마지막 줄에는 출발 층 A와 도착 층 B가 공백으로 구분되어 주어진다.
N은 100,000 이하, M은 100 이하의 자연수이다. Xi, Yi, A, B는 모두 N 이하의 자연수이며, A와 B는 서로 다르다.
출력
첫째 줄에 A층에서 B층으로 가기 위해 엘리베이터를 최소 몇 번 타야 하는지 출력한다.
이동할 수 있다면, 다음 줄부터 타야 하는 엘리베이터 번호를 한 줄에 하나씩 순서대로 출력한다. 가능한 순서가 여러 가지라면 그중 아무거나 출력해도 된다.
A층에서 B층으로 갈 수 없다면 첫째 줄에 -1만 출력한다.