Quality of Life Index

Consider the indices used to rank countries, such as the Human Development Index, the Democracy Index, the Freedom Index, and the Happiness Index.

These indices usually work as follows. For each country, $k$ statistical indicators $X_1, \ldots, X_k$ are collected, for example life expectancy, average years of schooling, and gross domestic product. Each indicator $X_i$ is given a weight $\lambda_i$. The index value of a country is $\lambda_1 X_1 + \cdots + \lambda_k X_k$, and countries are ranked by this value.

Such indices are often criticized for arbitrary weights. The person who builds an index may choose weights that produce the ranking they want.

You are given $N$ countries, each with three indicators. You are also given $M$ requirements. Each requirement says that country $A$ must rank above country $B$, meaning the value of country $A$ must be strictly greater than the value of country $B$. Determine whether there exist non-negative real weights $\lambda_1, \lambda_2, \lambda_3$ that satisfy all requirements.

The first line contains the number of tests $T$ ($1 \le T \le 100\,000$).

The first line of each test contains the number of countries $N$ ($2 \le N \le 100\,000$) and the number of requirements $M$ ($1 \le M \le 100\,000$).

Each of the next $N$ lines contains three integers $X_1$, $X_2$, and $X_3$ ($0 \le X_1 \le 10\,000$, $0 \le X_2 \le 10\,000$, $0 \le X_3 \le 10\,000$), the statistics of one country. Countries are numbered $1$ to $N$ in the order they appear in the input.

Each of the next $M$ lines contains two distinct integers $A$ and $B$ ($1 \le A \le N$, $1 \le B \le N$, $A \ne B$), meaning country $A$ must rank above country $B$.

The sum of $N$ over all tests is at most $100\,000$. The sum of $M$ over all tests is also at most $100\,000$.

For each test, print on its own line JAH if there exist weights that make the ranking satisfy all requirements, or EI if no such weights exist.