casute

Casute

Nargy si Fumeanu au plecat la munte. Ei au o harta a muntelui, in care sunt identificate $N$ casute montane (numerotate cu numere distincte intre {$1$} si {$N$}), situate la diferite inaltimi (casuta $i$ se afla la inaltimea {$H{~i~}$}). Aceste casute sunt legate prin $M$ poteci. O poteca leaga doua casute distincte si poate fi parcursa doar intr-un singur sens: de la casuta situata la o inaltime mai mica catre casuta situata la o inaltime mai mare.
La un moment dat, cei doi s-au despartit si fiecare a ajuns in dreptul unei casute, dar din fericire fiecare avea la el o copie a hartii. Cei doi si-au telefonat si au stabilit un loc de intalnire, astfel: se vor intalni la casuta situata la inaltimea minima dintre acele casute la care pot ajunge amandoi (tineti minte ca nu pot decat urca).

Pentru a evita astfel de situatii in viitor, cei doi si-au propus sa determine locul in care s-ar fi intalnit indiferent de casutele in care s-ar fi aflat cei doi. Ei vor trece aceste rezultate pe o foaie de hartie,  pentru fiecare pereche $i$ $j$ ({$1 &le; i < j &le; N$}), perechile fiind considerate in ordine lexicografica. in cazul in care pentru o anumita pereche nu exista o astfel de casuta de intalnire, se va scrie pe foaie numarul {$0$}.

Pentru a evita astfel de situatii in viitor, cei doi si-au propus sa determine locul in care s-ar fi intalnit indiferent de casutele in care s-ar fi aflat cei doi. Ei vor trece aceste rezultate pe o foaie de hartie, pentru fiecare pereche $i$ $j$ ({$1 &le; i < j &le; N$}), perechile fiind considerate in ordine lexicografica. In cazul in care pentru o anumita pereche nu exista o astfel de casuta de intalnire, se va scrie pe foaie numarul {$0$}.

h2. Date de intrare

== include(page="template/taskfooter" task_id="casute") ==

== SmfTopic(topic_id="1965") ==

1965