시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB1000.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.

예제 입력 1

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

예제 출력 1

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$.