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 그리고 엘리베이터 운행 정보가 주어질 때 철수가 최소 몇 번 엘리베이터를 타야하는지와 타야할 엘리베이터의 순서를 구하는 프로그램을 작성하시오.