엘리베이터

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만 출력한다.