Obiective Turistice

În judeţul Constanţa se găsesc cel mult $2\ 500$ de obiective turistice dispuse pe o suprafaţă asemănătoare cu un caroiaj, format din pătrăţele având latura de $1$ kilometru. Obiectivele sunt amplasate în unele puncte de intersecţie ale caroiajului.

Două obiective se consideră vecine dacă sunt situate pe una din direcţiile Nord, Sud, Est, Vest la o distanţă de $1$ kilometru una faţă de alta.

Între anumite perechi de obiective vecine au fost construite drumuri directe, pentru a se asigura deplasarea între oricare două obiective.

Despre fiecare obiectiv avem următoarele informaţii:

• numărul asociat acestuia, care este unic şi are o valoare cuprinsă între $1$ şi numărul total al obiectivelor;
• obiectivele vecine cu care acesta este conectat prin drumuri directe (cel mult patru obiective).

Pentru fiecare două obiective care comunică se cunoaşte costul asfaltării drumului direct dintre ele.

Cerință

Scrieți un program care rezolvă următoarele cerințe:

1. Se doreşte realizarea unei hărţi a judeţului în care să apară reprezentate toate obiectivele. Harta se va reprezenta sub forma unei matrice având dimensiunea maximă $51 \times 51$. Fiecare element al matricei codifică printr-o succesiune de patru cifre binare existenţa drumurilor directe care încadrează un pătrăţel din caroiaj. Dacă pe latura din nord a acestui pătrăţel există un drum direct între două obiective, atunci bitul cel mai semnificativ va fi $1$. În caz contrar acesta va fi $0$. Ceilalţi trei biţi corespund, în ordine, direcţiilor Sud, Est, Vest. De exemplu, dacă pentru un pătrăţel există drumuri pe laturile Nord, Sud şi Vest, cei patru biţi vor fi: $1$, $1$, $0$, $1$. Harta trebuie să aibă suprafaţă minimă dar să cuprindă toate obiectivele.
2. Se doreşte asfaltarea unora dintre drumurile existente astfel încât să se poată ajunge, mergând numai pe drumuri asfaltate de la oricare obiectiv la oricare altul. Costul total al asfaltării trebuie să fie minim. Să se precizeze care dintre drumuri vor fi asfaltate.

Date de intrare

În fişierul de intrare ob.in se află pe prima linie numărul $C$, care reprezintă cerința care trebuie rezolvată.

Urmează un număr necunoscut de linii până la sfârșitul fișierului, fiecare fiind de forma:
NO nvN cdsN nvS cdsS nvE cdsE nvV cdsV
având semnificaţia:

• NO = număr obiectiv;
• nvN = număr obiectiv vecin nord;
• cdsN = cost drum spre nord;
• nvS = număr obiectiv vecin sud;
• cdsS = cost drum spre sud;
• nvE = număr obiectiv vecin est;
• cdsE = cost drum spre est;
• nvV = număr obiectiv vecin vest;
• cdsV = cost drum spre vest.

Dacă un anumit obiectiv nu are vecin într-o anumită direcţie, numărul vecinului din direcţia respectivă va fi înlocuit cu $0,$ iar costul drumului direct dintre cele două cu $0$.

Valorile de pe o singură linie sunt separate prin unul sau mai multe spații.

Date de ieșire

Datele de ieşire se scriu în fişierul ob.out.

Dacă $C=1$, se afișează o hartă a obiectivelor folosind numere între $0$ şi $15$. Fiecare număr reprezintă codificarea în baza zece a celor patru cifre binare.

Dacă $C=2$, se afișează pe prima linie costul optim cerut şi pe următoarele linii obiectivele între care se asfaltează drumul.

Restricții și precizări

• Numărul de obiective este cel mult $2\ 500$.
• Harta se încadrează într-o matrice de $51$ de linii şi $51$ de coloane.
• Lungimile drumurilor directe sunt cel mult $100$.
• Drumurile directe între obiective sunt bidirecţionale.
• Se garantează că datele de intrare nu conţin date incompatibile.
• Primele 10 teste sunt în valoare de 50 de puncte și au $C = 1$; următoarele 10 teste sunt în valoare de 50 de puncte și au $C = 2$.

Exemplul 1

ob.in

1
1 0 0 0 0 2 3 0 0
3 6 3 0 0 0 0 2 1
6 0 0 3 3 0 0 5 2
2 5 2 0 0 3 1 1 3
4 0 0 0 0 5 3 0 0
5 0 0 2 2 6 2 4 3

ob.out

2 7 5
2 11 9

Exemplul 2

ob.in

2
1 0 0 0 0 2 3 0 0
3 6 3 0 0 0 0 2 1
6 0 0 3 3 0 0 5 2
2 5 2 0 0 3 1 1 3
4 0 0 0 0 5 3 0 0
5 0 0 2 2 6 2 4 3

ob.out

11
1 2
2 3
6 5
2 5
5 4

Explicație

Ambele exemple corespund hărții de mai jos: