Problem
Vasyuki 지역의 일부 마을 사이에는 버스가 있습니다. 이곳은 승객이 많지 않기 때문에 버스는 하루에 몇 번만 운행합니다.
마리아 이바노브나는 가능한 한 빨리 d 마을에서 v 마을로 이동해야 합니다(그녀는 시간 0에 d 마을에 있는 것으로 간주됩니다).
입력
먼저 숫자 N을 입력하십시오 – 총 마을 수(1 <= N <= 100), 그런 다음 마을 번호 d와 v, 다음에 버스 여행 횟수 R(0 <= R <= 10000)이 뒤따릅니다. 다음은 버스 노선에 대한 설명입니다. 각 항공편은 출발 마을 번호, 출발 시간, 도착 마을 및 도착 시간(모든 시간은 0에서 10000까지의 정수임)으로 제공됩니다. 승객이 시간 t에 어떤 마을에 도착하면 t부터 시작하여 언제든지 떠날 수 있습니다.
출력
Maria Ivanovna가 마을에 있을 수 있는 최소 시간을 인쇄하십시오. v. 그녀가 주어진 버스 노선을 사용하여 d에서 v로 갈 수 없다면 -1을 인쇄하십시오.
예
<헤드>
<일>#
| 입력 |
출력 |
<몸>
| 1 |
<사업부>3
1 3
<사업부>4
1 0 2 5
1 1 2 3
2 3 3 5
1 1 3 10
|
5 |