기차 여행
시간 제한4초메모리 제한1024 MB
도시마다 [L_i, R_i] 구간을 오가는 열차가 있을 때 U에서 V까지 가는 데 필요한 최소 열차 수를 구하고, 불가능하면 -1을 출력합니다.
문제
복잡하고 머리 아픈 경기과학고에서의 생활에 지친 재민이는 어디론가 떠나기로 결심했다. 그래서 재민이는 조용한 휴양지를 찾아 송죽국으로 아주 긴 여행을 떠나기로 했다.
송죽국은 개의 도시가 일렬로 늘어서 있는 평화로운 나라이다. 도시에는 가장 끝의 1번 도시부터 번 도시까지 순서대로 번호가 매겨져 있다.
재민이는 송죽국의 관광상품인 송죽 열차를 타고 여행하려고 한다. 각 도시에서는 한 종류의 기차를 탈 수 있으며, 기차는 정해진 선로를 따라 운행한다. 구체적으로, 번 도시에서 출발하는 열차는 번 도시부터 번 도시 사이의 도시들을 모두 지나가는 순환선으로 운영된다. 승객은 기차가 지나가는 동안 어느 도시에서든 내릴 수 있지만, 지나가는 열차에 중간에 탑승하는 것은 불가능하다.
재민이는 여행 중 개의 이동 계획을 세웠다. 번째 이동 계획은 번 도시에서 번 도시까지 송죽 열차만 타고 이동하는 것이다.
재민이는 시간과 돈을 아끼고 싶어서 각 이동 계획에서 열차를 갈아타는 횟수를 최대한 줄이려고 한다. 이 문제에서 할 일은 각 이동 계획을 열차만으로 수행할 수 있는지 확인하고, 수행할 수 있다면 타야 하는 열차의 최소 개수를 구하는 것이다.
입력
첫 줄에 , 가 공백으로 구분되어 주어진다.
이후 개의 줄에 , 가 차례대로 공백으로 구분되어 주어진다.
이후 개의 줄에 , 가 차례대로 공백으로 구분되어 주어진다.
출력
주어진 각 이동 계획을 실행하기 위해 타야 하는 열차의 최소 개수를 한 줄에 하나씩 총 줄에 출력한다. 이동 계획을 열차만으로 수행할 수 없다면 열차 수 대신 -1을 출력한다.