Karaván

Egy sivatagban N város található, melyek között az év egy időszakában naponta indulnak karavánok. Ezen időszakon kívül azonban egyetlen sem indul.

Feladat:

Készíts programot, amely meghatározza két adott, A B városra és H határidőre a következőket:

· Legkorábban mikorra érhetünk az A városból a B városba;

· Legalább hány nap kell ahhoz, hogy az A városból a B városba érjünk, ha nincs megkötés sem az indulási, sem az érkezési időre;

· Legkésőbb melyik napon kell elindulni az A városból, hogy legkésőbb a megadott H határidőig a B városba érjünk.

Bemenet:

A KARAVAN.BE állomány első sorában a városok száma (1<=N<=100) és a karavánkapcsolatok száma (1<=M<=5000) van. A következő M sor mindegyikében két város-sorszám (X,Y) és két napsorszám (P,Q) van egy-egy szóközzel elválasztva, ami azt jelenti, hogy az X. városból az Y városba az év P. és Q. napja között (P-t és Q-t is beleértve) indulnak karavánok. Az állomány utolsó sorában az indulási (A) és az érkezési (B) hely sorszáma van, valamint annak a napnak az éven belüli H sorszáma, amikor legkésőbb meg kell érkezni a B. városba, egy-egy szóközzel elválasztva. A karavánok mindig reggel indulnak és még aznap este megérkeznek a célállomásra.

Kimenet:

A KARAVAN.KI állományba három sort kell írni. Minden sorban egyetlen szám szerepeljen: a részfeladat megoldásának értéke. Ha egy részfeladatnak nem létezik megoldása, akkor a -1 számot kell kiírni.

Példa:

KARAVAN.BE

KARAVAN.KI

5 7
1 2 2 7
1 5 2 4
2 3 1 2
2 5 8 9
3 4 6 7
5 4 3 9
4 2 1 2
1 4 10

(Nemes Tihamér 2000. döntő)