| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 1 | 0 | 0 | 0.000% |
Vaatleme indekseid, mille alusel riike pingeritta pannakse: inimarengu indeks, demokraatiaindeks, vabaduseindeks, õnnelikkuse indeks jne.
Need toimivad üldiselt järgmiselt: iga riigi kohta kogutakse $k$ statistilist näitajat $X_1, \ldots, X_k$ (näiteks keskmine eluiga, keskmine haridustase, sisemajanduse kogutoodang jne); igale näitajale $X_i$ määratakse kaal $\lambda_i$; riik saab indeksi väärtuseks arvu $\lambda_1 X_1 + \cdots + \lambda_k X_k$ ja nende arvude järgi pannaksegi riigid pingeritta.
Selliseid indekseid on sageli kritiseeritud kaalude meelevaldsuse tõttu: on täiesti võimalik, et indeksi koostaja on valinud kaalud selliselt, et tulemus on talle meelepärane.
Sulle on antud $N$ riiki ja iga riigi kohta kolm näitajat. Lisaks on antud $M$ nõuet kujul "riik $A$ peab pingereas olema riigist $B$ eespool" (riigi $A$ tulemus peab olema rangelt suurem riigi $B$ tulemusest). Sinu ülesandeks on kindlaks teha, kas leiduvad sellised mittenegatiivsed reaalarvulised kaalud $\lambda_1, \lambda_2, \lambda_3$, et kõik nõuded oleks rahuldatud.
Selles ülesandes võib sisend koosneda mitmest alamtestist. Sisendi esimesel real on alamtestide arv $T$ ($1 \le T \le 100\,000$).
Iga alamtesti esimesel real on antud riikide arv $N$ ($2 \le N \le 100\,000$) ja nõuete arv $M$ ($1 \le M \le 100\,000$).
Järgmisel $N$ real on igaühel kolm täisarvu $X_1$, $X_2$ ja $X_3$ ($0 \le X_1 \le 10\,000$, $0 \le X_2 \le 10\,000$, $0 \le X_3 \le 10\,000$): ühe riigi statistilised näitajad. Riigid on nummerdatud $1, \ldots, N$ nende andmete sisendis loetlemise järjekorras.
Järgmisel $M$ real on igaühel kaks erinevat täisarvu $A$ ja $B$ ($1 \le A \le N$, $1 \le B \le N$, $A \ne B$), mis tähendab, et riik $A$ peab pingereas olema riigist $B$ eespool.
Riikide arvude summa kõikide alamtestide peale kokku on maksimaalselt $100\,000$. Nõuete arvude summa kõikide alamtestide peale kokku on samuti maksimaalselt $100\,000$.
Iga alamtesti kohta väljastada eraldi reale sõna JAH, kui leiduvad kaalud, mille korral saadud pingerida rahuldab kõiki nõudeid, või sõna EI, kui selliseid kaale ei leidu.
3 4 3 0 5 1 0 4 2 0 2 3 0 8 1 2 1 3 2 4 2 3 2 1 2 5 5 1 1 3 1 3 3 1 3 2 4 4 4 1 9 7 0 2 1 4 4 3 4 8 1 2 1 3 4 1 2 3
JAH EI JAH
Näidissisend koosneb kolmest alamtestist. Esimeses alamtestis on sobivateks kaaludeks näiteks $\lambda_1 = 5$, $\lambda_2 = 3$, $\lambda_3 = 7$. Teises alamtestis ei ole võimalik leida selliseid kaale, et mõlemad nõuded oleksid rahuldatud. Kolmandas alamtestis on sobivateks kaaludeks näiteks $\lambda_1 = 2$, $\lambda_2 = 2$, $\lambda_3 = 1$.