삶의 질 지수

국가를 순위로 정렬할 때 쓰는 지수들을 살펴보자. 인간 개발 지수, 민주주의 지수, 자유 지수, 행복 지수 등이 그 예다.

이런 지수는 보통 다음과 같이 동작한다. 각 국가에 대해 $k$개의 통계 지표 $X_1, \ldots, X_k$를 모은다(예를 들어 평균 수명, 평균 교육 연수, 국내총생산 등). 각 지표 $X_i$에는 가중치 $\lambda_i$가 주어진다. 국가의 지수 값은 $\lambda_1 X_1 + \cdots + \lambda_k X_k$이며, 이 값의 크기 순서대로 국가를 줄 세운다.

이런 지수는 가중치를 임의로 정한다는 이유로 자주 비판받는다. 지수를 만든 사람이 자신에게 맞는 결과가 나오도록 가중치를 골랐을 수 있기 때문이다.

$N$개 국가와 각 국가의 지표 세 개가 주어진다. 또한 $M$개의 요구 조건이 주어진다. 각 조건은 국가 $A$가 순위에서 국가 $B$보다 앞에 있어야 한다는 뜻이며, 이때 국가 $A$의 값은 국가 $B$의 값보다 엄격하게 커야 한다. 모든 요구 조건을 만족하는 음이 아닌 실수 가중치 $\lambda_1, \lambda_2, \lambda_3$가 존재하는지 판단하라.

입력의 첫 줄에 테스트 수 $T$가 주어진다 ($1 \le T \le 100\,000$).

각 테스트의 첫 줄에는 국가 수 $N$ ($2 \le N \le 100\,000$)과 요구 조건 수 $M$ ($1 \le M \le 100\,000$)이 주어진다.

다음 $N$개 줄에는 각각 정수 $X_1$, $X_2$, $X_3$ ($0 \le X_1 \le 10\,000$, $0 \le X_2 \le 10\,000$, $0 \le X_3 \le 10\,000$)이 주어지며, 이는 한 국가의 통계 지표다. 국가는 입력에 나온 순서대로 $1$부터 $N$까지 번호가 붙는다.

다음 $M$개 줄에는 각각 서로 다른 두 정수 $A$와 $B$ ($1 \le A \le N$, $1 \le B \le N$, $A \ne B$)가 주어지며, 국가 $A$가 국가 $B$보다 순위에서 앞에 있어야 한다는 뜻이다.

모든 테스트에 걸친 국가 수의 합은 최대 $100\,000$이다. 모든 테스트에 걸친 요구 조건 수의 합도 최대 $100\,000$이다.

각 테스트에 대해 한 줄에 답을 출력한다. 모든 요구 조건을 만족하는 가중치가 존재하면 JAH, 존재하지 않으면 EI를 출력한다.