Artanis, comandantul navei „Spear of Adun”, trebuie să ia legătura cu centrul de comandă situat pe planeta Aiur. Mai exact, el trebuie să transmită un mesaj codificat printr-un bit. Acest mesaj va fi transmis de pe calculatorul aflat la bordul navei la calculatorul aflat în centrul de comandă de pe Aiur printr-o rețea intergalactică de calculatoare.
Rețeaua de calculatoare poate fi privită ca un graf orientat cu V noduri și E muchii. Fiecare muchie este de forma (x, y, p0, p1) și are semnificația: „calculatorul x poate transmite mesaje către calculatorul y, un bit de 0 este transmis corect cu probabilitate p0, iar un bit de 1 este transmis corect cu probabilitate p1”. Un bit este transmis corect dacă are aceeași valoare atât în calculatorul emițător, cât și în calculatorul receptor.
Atunci când un calculator primește un mesaj, va alege în mod aleator și cu aceeași probabilitate una dintre muchiile sale de ieșire și va transmite mesajul mai departe pe acea muchie.
Artanis ar vrea să afle probabilitatea ca bitul 0, respectiv 1, să fie transmiși corect de la calculatorul de pe „Spear of Adun” la calculatorul de pe Aiur.
Date de intrare
Pe prima linie a fișierului de intrare network.in se vor afla numerele V și E. Pe următoarele E linii se vor afla câte patru numere (x, y, p0, p1), semnificând o muchie din rețea.
Date de ieșire
În fișierul de ieșire network.out veți afișa pe prima linie probabilitatea ca bitul 0 să fie transmis corect, iar pe a doua linie veți afișa probabilitatea ca bitul 1 să fie transmis corect către calculatorul de pe Aiur.
Restricții și precizări
1 ≤ V ≤ 5 0000 ≤ E ≤ 50 0000 ≤ p0, p1 ≤ 1.0pentru toate muchiile, iar aceste probabilități vor fi date în fișierul de intrare cu cel mult două zecimale- Nu putem alege o submulțime de mai mult de
70de calculatoare astfel încât fiecare calculator din mulțime să fie accesibil din fiecare alt calculator din acea mulțime - Calculatoarele din rețea sunt reprezentate prin indici de la
0laV-1 - Calculatorul de pe nava „Spear of Adun” are numărul
0, iar calculatorul de pe Aiur are numărulV-1 - Calculatorul de pe Aiur va avea gradul de ieșire
0și va fi accesibil (direct sau indirect) de toate calculatoarele din rețea - Pentru oricare două calculatoare
xșiyva exista cel mult o muchie orientată de laxlayși cel mult o muchie orientată de laylaxși nu vor exista muchii de la un calculator la el însuși - Soluția se consideră corectă dacă diferă față de răspunsul corect cu cel mult
0.00001 - Se garantează că pentru teste în valoare de
20de puncte, nu vor exista două calculatoare distinctexșiyastfel încâtxsă fie accesibil dinyșiysă fie accesibil dinx - Se garantează că pentru teste în valoare de alte
40de puncte,V <= 100
Exemple
network.in
4 3
0 1 1.0 0.5
1 2 0.2 1.0
2 3 0.1 0.0
network.out
0.8200000
0.0900000
Explicaţii
Dacă transmitem bitul 1 de la nodul 0 la nodul 3, există o singură transmisie corectă, și anume: transmitem incorect bitul pe muchia (0→1) cu probabilitate 0.5. Astfel, la calculatorul 1 ajunge bitul 0. Transmitem corect bitul 0 de la calculatorul 1 la calculatorul 2 pe muchia (1→2) cu probabilitate 0.2. Astfel, la calculatorul 2 ajunge bitul 0. Transmitem incorect bitul 0 de la calculatorul 2 la calculatorul 3 pe muchia (2→3) cu probabilitate 0.9. Astfel, la calculatorul de pe Aiur ajunge bitul 1 cu probabilitate 0.5 * 0.2 * 0.9 = 0.09. Se procedează similar dacă dorim să transmitem bitul 0 la calculatorl de pe Aiur.