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_1$, $p_2$ i $p_3$, 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 \ldots 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 \le n \le 10$, $0 \le m \le 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.