LED 회로

발광 다이오드(LED, light-emitting diode)는 애노드와 캐소드라고 부르는 두 단자를 가진 전자 부품이다. 그림 왼쪽의 A와 K가 각각 애노드와 캐소드이다. 애노드의 전압이 캐소드보다 높으면(그림 (a)) LED에 불이 켜진다. 캐소드의 전압이 애노드보다 높으면(그림 (b)) LED는 켜지지 않지만 고장 나지도 않는다. 애노드와 캐소드의 전압이 같아도(그림 (c)와 (d)) LED는 켜지지 않는다.

Juku는 여러 LED와 이를 제어하는 컨트롤러를 가지고 있다. 컨트롤러에는 $N$개의 출력이 있으며 $1 \ldots N$의 번호가 붙어 있다. 각 출력에는 프로그램으로 높은 전압 또는 낮은 전압(그림에서 각각 1과 0)을 걸 수 있고, 이를 통해 컨트롤러에 연결된 LED의 켜짐을 조절한다.

Juku는 각 LED를 다른 LED와 독립적으로 켤 수 있도록 많은 LED를 컨트롤러에 연결하려고 한다. 즉, 그 LED만 켜진 상태를 만들 수 있어야 한다. 예를 들어 아래 그림 왼쪽 회로에서는 두 LED를 각각 따로 켤 수 있다. 오른쪽 회로에서는 두 LED가 항상 함께 켜진다.

Juku의 회로 설명을 입력받아, 이 회로로 어떤 LED를 다른 LED와 독립적으로 켤 수 있는지 구하는 프로그램을 작성하라.

첫 줄에 컨트롤러 출력의 개수 $N$ ($2 \le N \le 250$)과 LED의 개수 $M$ ($1 \le M \le 25\,000$)이 주어진다. 다음 $M$개 줄에는 각각 공백으로 구분된 두 정수 $A_i$, $B_i$ ($1 \le A_i, B_i \le N$, $A_i \ne B_i$)가 주어진다. 이는 $i$번째 LED의 애노드가 출력 $A_i$에, 캐소드가 출력 $B_i$에 연결되어 있다는 뜻이다.

LED마다 한 줄씩 출력한다. 컨트롤러 출력에 전압을 적절히 걸어 $i$번째 LED만 켜지도록 할 수 있으면 $i$번째 줄에 JAH를, 그렇지 않으면 EI를 출력한다.