Elukvaliteediindeks

문제

Vaatleme indekseid, mille alusel riike pingeritta pannakse: inimarengu indeks, demokraatiaindeks, vabaduseindeks, õnnelikkuse indeks jne.

Need toimivad üldiselt järgmiselt: iga riigi kohta kogutakse $kk$ statistilist näitajat $X_1,\dots ,X_{k}X\_1,\; \backslash ldots,\; X\_k$ (näiteks keskmine eluiga, keskmine haridustase, sisemajanduse kogutoodang jne); igale näitajale $X_{i}X\_i$ määratakse kaal ${\lambda }_i\backslash lambda\_i$; riik saab indeksi väärtuseks arvu ${\lambda }_1{X}_1+\cdots +{\lambda }_k{X}_k\backslash lambda\_1\; X\_1\; +\; \backslash cdots\; +\; \backslash 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 $NN$ riiki ja iga riigi kohta kolm näitajat. Lisaks on antud $MM$ nõuet kujul "riik $AA$ peab pingereas olema riigist $BB$ eespool" (riigi $AA$ tulemus peab olema rangelt suurem riigi $BB$ tulemusest). Sinu ülesandeks on kindlaks teha, kas leiduvad sellised mittenegatiivsed reaalarvulised kaalud ${\lambda }_1,{\lambda }_2,{\lambda }_3\backslash lambda\_1,\; \backslash lambda\_2,\; \backslash lambda\_3$, et kõik nõuded oleks rahuldatud.

입력

Selles ülesandes võib sisend koosneda mitmest alamtestist. Sisendi esimesel real on alamtestide arv $TT$ ($1\le T\le 1000001\; \backslash le\; T\; \backslash le\; 100\backslash ,000$).

Iga alamtesti esimesel real on antud riikide arv $NN$ ($2\le N\le 1000002\; \backslash le\; N\; \backslash le\; 100\backslash ,000$) ja nõuete arv $MM$ ($1\le M\le 1000001\; \backslash le\; M\; \backslash le\; 100\backslash ,000$).

Järgmisel $NN$ real on igaühel kolm täisarvu $X_{1}X\_1$, $X_{2}X\_2$ ja $X_{3}X\_3$ ($0\le X_1\le 100000\; \backslash le\; X\_1\; \backslash le\; 10\backslash ,000$, $0\le X_2\le 100000\; \backslash le\; X\_2\; \backslash le\; 10\backslash ,000$, $0\le X_3\le 100000\; \backslash le\; X\_3\; \backslash le\; 10\backslash ,000$): ühe riigi statistilised näitajad. Riigid on nummerdatud $1,\dots ,N1,\; \backslash ldots,\; N$ nende andmete sisendis loetlemise järjekorras.

Järgmisel $MM$ real on igaühel kaks erinevat täisarvu $AA$ ja $BB$ ($1\le A\le N1\; \backslash le\; A\; \backslash le\; N$, $1\le B\le N1\; \backslash le\; B\; \backslash le\; N$, $A\mathrm{\ne }BA\; \backslash ne\; B$), mis tähendab, et riik $AA$ peab pingereas olema riigist $BB$ eespool.

Riikide arvude summa kõikide alamtestide peale kokku on maksimaalselt $100000100\backslash ,000$. Nõuete arvude summa kõikide alamtestide peale kokku on samuti maksimaalselt $100000100\backslash ,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