Procesors

ID: proc
Grūtība: 2/5
Laika limits: 1

Uzdevums

Firma MegaPro pēdējā brīdī pirms sava procesora sērijveida ražošanas atrada, ka tajā trūkst viens savienojums starp punktiem A un B (kreisajā zīmējumā). Lai sāktu sērijveida ražošanu, nepieciešams izveidot trūkstošo savienojumu (labajā zīmējumā). Procesors sastāv no punktiem, kas atrodas tīkla krustojumos, kā arī to savienojumiem. Savienojumi sastāv no posmiem, pie tam katrs posms ir kādas rūtiņas mala.

Ievaddati

Teksta faila proc.in pirmajā rindā doti divi veseli skaitļi X un Y (1 <= X,Y <= 100) - tīkla platums un augstums un izveidoto posmu skaits N. Sekojošās N rindās atrodas katra posma sākumpunkta un beigu punkta koordinātas xi1 yi1 xi2 yi2 (0 <= xi1 <= X, 0 <= yi1 <= Y, 0 <= xi2 <= X, 0 <= yi2 <= Y). Pēdējā rindā atrodas to punktu, kas jāsavieno, koordinātas xA yA xB yB (0 <= xA <= X, 0 <= yA <= Y, 0 <= xB <= X, 0 <= yB <= Y). Šie punkti nav savienoti ne ar vienu citu punktu. Kreisā apakšējā stūra koordinātas ir pāris 0 0, bet labā augšējā - pāris X Y.

Izvaddati

Teksta faila proc.out pirmajā rindā jāizvada vārds NEVAR, ja nepieciešamo savienojumu izveidot nav iespējams. Ja tas ir iespējams, tad jāizvada minimālais posmu skaits, pievienojot kurus tiek izveidots nepieciešamais savienojums.

Piemērs

proc.in proc.out
4 2 5
0 1 0 2
0 2 1 2
2 0 3 0
3 0 3 1
3 0 4 0
0 0 4 2
6


© 2001-2002 olimps! http://www.lio.lv/olimps/