Se dau doi arbori neorientaţi cu noduri etichetate de la la şi costuri pe muchii. Primul arbore se numeşte TREN, iar al doilea se numeşte BUS. Pentru două noduri şi şi un arbore definim = valoarea maximă a unei muchii de pe drumul elementar dintre nodurile şi în arborele .
Suntem interesaţi de perechile de valori şi cu proprietatea că este minim posibil.
În funcţie de valoarea unui parametru din datele de intrare, trebuie să afişaţi suma minimă cerută, respectiv numărul de perechi de valori care se realizează această valoare minimă.
Date de intrare
Pe primul rând al fişierului de intrare trenbus.in se găsesc numerele naturale şi .
Pe următoarele rânduri se găsesc muchiile neorientate care descriu arborele TREN, iar pe următoarele rânduri se găsesc muchiile neorientate care descriu arborele BUS. Fiecare muchie este descrisă de numere naturale , reprezentând capetele muchiei respectiv costul.
Date de ieșire
Pe singurul rând al fişierului de ieşire trenbus.out se vor tipări:
- dacă , doar suma cerută,
- dacă , suma cerută şi numărul de perechi separate printr-un spaţiu.
Restricții și precizări
- Pentru teste în valoare de puncte si
- Pentru alte teste în valoare de puncte si
- Pentru alte teste în valoare de puncte si
- Pentru alte teste în valoare de puncte si
- Pentru alte teste în valoare de puncte si
Exemplul 1
trenbus.in
1 3
1 2 5
2 3 6
1 3 1
2 3 2
trenbus.out
7
Explicație
, se afişează doar suma minimă. Generată de , sau respectiv , .
Exemplul 2
trenbus.in
2 5
1 2 2
2 5 3
2 4 7
2 3 2
1 2 4
2 3 4
3 4 3
4 5 2
trenbus.out
6 4
Explicație
; Suma minimă este , iar numărul perechilor de noduri ce generează această sumă minimă este .