Porra P72480

Una gran tradició del SWERC és fer una porra sobre com quedaran els tres equips de la UPC. Típicament, cada aposta consisteix en tres enters diferents p₁, p₂ i p₃, on p_i és la posició pronosticada per a UPC i. El guanyador és qui té una suma de distàncies a les posicions finals més petita. En cas d’empat a suma mínima de distàncies, tots els empatats guanyen.

Enguany un dels membres dels equips UPC ha “stalkejat” a la resta d’equips participants. Amb tota la informació aconseguida pot assegurar les posicions relatives d’alguns equips, és a dir, pot saber que l’equip x guanyarà a l’equip y, per a m parells de x i y. En total hi ha n equips, numerats entre 0 i n−1. L’equip UPC i és el i − 1.

Donada la informació de què es disposa i les 9 apostes dels membres dels equips UPC, quin d’ells té més probabilitats de guanyar? Suposeu que totes les classificacions (permutacions de {1 … n}) que són consistents amb les m restriccions són equiprobables.

Entrada

L’entrada consisteix en diversos casos, cadascun amb n i m. A continuació venen m parelles diferents d’enters x i y, tal i com s’ha explicat anteriorment. Finalment, tenim les 9 apostes dels membres dels equips UPC. Suposeu 3 ≤ n ≤ 10, 0 ≤ m ≤ n(n−1)/2, i que les m ‍restriccions donades són consistents amb almenys una classificació.

Sortida

Per a cada cas, escriviu els membres amb més probabilitats de guanyar. En cas que n’hi hagi més d’un, s’han d’escriure en ordre creixent. Els membres s’identifiquen entre 0 i 8.