Simulare OJI VII | campionat

Ne aflăm la un anumit moment al desfășurării campionatului național de fotbal. O parte dintre meciuri s-au jucat, altele urmează să fie disputate. Se cunoaște numărul de puncte acumulate deja de fiecare echipă înaintea desfășurării meciurilor restante. Se cunoaște, de asemenea, că un meci se poate termina egal, caz în care fiecare dintre echipe primește câte un punct, sau cu victoria uneia dintre echipe, iar în acest caz acea echipă primește trei puncte, iar cealaltă zero puncte.

Cerință

Avem de răspuns la întrebări de două tipuri:

1. Care echipe ar fi pe locul I dacă toate meciurile restante s-ar termina la egalitate? O echipă este pe locul I dacă are număr maxim de puncte.
2. Care echipe depind strict de propriile rezultate pentru a deveni campioane? O echipă devine campioană (câștigă campionatul) dacă termină cu număr de puncte strict mai mare decât oricare dintre celelalte echipe. Spunem că o echipă depinde strict de propriile rezultate pentru a deveni campioană dacă ea devine campioană câștigând toate meciurile pe care trebuie să le mai joace, indiferent de rezultatele celorlalte meciuri.

Date de intrare

Fișierul de intrare campionat.in conține pe prima linie un număr $T$, reprezentând tipul de întrebare ($1$ sau $2$). Pe linia a doua se află un număr $N$ reprezentând numărul de echipe din campionat (considerăm că echipele sunt etichetate cu numere distincte de la $1$ la $N$). Pe linia a treia se află $N$ numere naturale separate prin câte un spațiu, al $i$-lea număr reprezentând punctajul celei de-a $i$-a echipe. Pe linia a patra se află un număr $D$, reprezentând numărul de meciuri restante. Pe fiecare dintre următoarele $D$ linii se află câte două numere distincte $i, j$, cuprinse între $1$ și $N$, cu semnificația că echipele $i$ și $j$ au de disputat un meci restant.

Date de ieșire

Fișierul de ieșire campionat.out va conține o singură linie.

Dacă $T = 1$, linia va conține etichetele echipelor care termină pe locul I, în cazul în care toate meciurile restante se termină la egalitate.
Dacă $T = 2$, linia va conține etichetele echipelor care depind strict de propriile rezultate pentru a deveni campioane. Dacă nicio echipă nu poate deveni campioană depinzând doar de rezultatele sale, în fișierul de ieșire se va scrie doar numărul $0$.
Atât pentru $T = 1$, cât și pentru $T = 2$ etichetele echipelor vor fi scrise în ordine crescătoare, separate prin câte un spațiu.

Restricții și precizări

• $2 \leq N \leq 1 \ 000$;
• $1 \leq D \leq 500 \ 000$;
• Punctajele inițiale ale echipelor sunt numere naturale cel mult egale cu $1 \ 000$.
• Regulile de desfășurare a campionatului sunt mai ciudate, nu trebuie să vă puneți problema dacă este posibil ca echipele să aibă șirul dat al punctajelor în urma meciurilor disputate deja (considerăm că până la momentul de față federația a acordat diverse bonusuri și depunctări).
• Dacă între meciurile rămase de jucat este vreunul care apare de mai multe ori (fie sub forma $(i, j)$ fie sub forma $(j, i)$), el se va disputa o singură dată.
• Programarea meciurilor s-a făcut în mod indisciplinat, deci este posibil ca unele echipe să mai aibă de jucat mai multe meciuri decât altele, iar unele chiar să nu mai aibă de jucat niciun meci.
• Pentru teste valorând $22$ de puncte, $T = 1$.
• Pentru alte teste valorând $9$ puncte, $T = 2$ și fiecare echipă are de disputat exact $2$ meciuri cu alte echipe.
• Pentru alte teste valorând $8$ puncte, $T = 2$ și fiecare echipă are de disputat câte un meci cu fiecare altă echipă.
• Pentru alte teste valorând $10$ puncte, $T = 2$ și există o singura echipă care joacă câte un meci cu fiecare altă echipă, celelalte echipe neavând alte meciuri restante de jucat.

Exemplul 1

campionat.in

1
4
2 3 2 1
3
1 3
1 2
3 1

campionat.out

1 2

Explicație

Echipa $2$ are de disputat un singur meci cu echipa $1$, iar al doilea meci se va disputa între echipele $1$ și $3$ (chiar dacă în listă apare de două ori perechea $1 \ 3$, este vorba despre un singur meci).
Cele două jocuri se vor termina la egalitate, și astfel punctajele echipelor la final vor fi: $4 \ 4 \ 3 \ 1$. Așadar echipele $1$ și $2$ ies pe primul loc.

Exemplul 2

campionat.in

2
4
1 3 2 1
3
1 3
1 2
3 1

campionat.out

1 2

Explicație

Echipa $1$ devine campioană dacă învinge în ambele meciuri, nicio altă echipă neputând să o egaleze la puncte sau să o depășească.

De asemenea, echipa $2$ devine campioană dacă învinge echipa $1$ în meciul restant, indiferent de rezultatul celuilalt meci. Echipa $3$, chiar dacă învinge în meciul cu echipa $1$, nu depinde doar de rezultatul său întrucât echipa $2$ ar depăși-o la puncte dacă și ea ar câștiga meciul pe care îl mai are de disputat.