题目描述

我们考虑一些用来给国家排名的指数：人类发展指数、民主指数、自由指数、幸福指数，等等。

这些指数通常按照如下方式工作：对每个国家收集 $k$ 个统计指标 $X_1,\ldots,X_k$，例如平均寿命、平均受教育水平、国内生产总值等；对每个指标 $X_i$ 赋予一个权重 $\lambda_i$；该国家的指数值为

$$\lambda_1X_1+\cdots+\lambda_kX_k$$

然后按这些指数值对国家排序。

这类指数经常因为权重的任意性而受到批评：指数制定者完全可能选择一组权重，使得最终结果符合自己的偏好。

现在给定 $N$ 个国家，并且每个国家有三个指标。此外，给定 $M$ 条要求，每条要求形如“国家 $A$ 必须在排名中排在国家 $B$ 前面”，也就是说，国家 $A$ 的指数值必须严格大于国家 $B$ 的指数值。

你的任务是判断是否存在一组三个非负实数权重 $\lambda_1,\lambda_2,\lambda_3$，使得所有要求都被满足。

输入格式

本题输入可能包含多个子测试。

第一行包含子测试数量 $T$。

$$1\le T\le 100000$$

每个子测试的第一行包含两个整数 $N$ 和 $M$，分别表示国家数量和要求数量。

$$2\le N\le 100000,\quad 1\le M\le 100000$$

接下来 $N$ 行，每行包含三个整数 $X_1,X_2,X_3$，表示一个国家的统计指标。

$$0\le X_1\le 10000,\quad 0\le X_2\le 10000,\quad 0\le X_3\le 10000$$

国家按它们在输入中出现的顺序编号为 $1,\ldots,N$。

接下来 $M$ 行，每行包含两个不同的整数 $A$ 和 $B$。

$$1\le A\le N,\quad 1\le B\le N,\quad A\ne B$$

这表示国家 $A$ 必须在排名中位于国家 $B$ 之前。

所有子测试的国家数量总和最多为 $100000$。所有子测试的要求数量总和也最多为 $100000$。

输出格式

对每个子测试，输出单独一行。

如果存在一组权重，使得所得排名满足所有要求，则输出 JAH；否则输出 EI。

样例

输入

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

样例解释

样例输入包含三个子测试。

在第一个子测试中，一组可行的权重例如为 $\lambda_1=5,\lambda_2=3,\lambda_3=7$。

在第二个子测试中，不可能找到同时满足两条要求的权重。

在第三个子测试中，一组可行的权重例如为 $\lambda_1=2,\lambda_2=2,\lambda_3=1$。

评分方式

本题测试数据分组。只有通过某个组内所有测试的解法，才能获得该组分数。各组的额外限制如下：

1. （$10$ 分）在所有子测试中，所有国家都有 $X_1=X_2=0$。
2. （$15$ 分）在所有子测试中，所有国家都有 $X_1\le 2$、$X_2\le 2$ 且 $X_3\le 2$；所有子测试的要求数量总和最多为 $100$。
3. （$15$ 分）在所有子测试中，$M\le 2$。
4. （$20$ 分）在所有子测试中，所有国家都有 $X_1=0$。
5. （$40$ 分）没有额外限制。