시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 842 168 126 28.636%

문제

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

예제 입력 1

12 3
4 3
7 5
4 4
10 8

예제 출력 1

2
1
3

출처

Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2005 > 중등부 4번

  • 데이터를 추가한 사람: chogahui05
  • 빠진 조건을 찾은 사람: ls4154