인터넷 독점

매우 자랑스러운 왕국에는 $N$개의 도시가 있고, 도시 번호는 $1, \ldots, N$이다.

나라의 모든 인터넷 케이블은 Internet Operations Incorporated(IOI)가 관리한다. 인터넷 서비스 제공업체는 IOI에서 케이블 사용권을 임대한다.

IOI의 가격표는 다음과 같다. 일부 케이블의 연간 임대료는 $100\,000$유로이고, 나머지 케이블은 $200\,000$유로이다. 각 서비스 제공업체는 모든 도시가 직접 또는 간접으로 서로 연결되도록 케이블을 임대하며, 임대료 총액은 가능한 한 낮게 맞춘다. IOI는 모든 임차인이 정확히 같은 케이블 집합을 임대하기를 원한다. 그래야 케이블 망을 관리하기 쉽기 때문이다.

IOI는 때때로 새 케이블을 설치한다. 그때마다 다음 질문이 생긴다. 연간 임대료가 $100\,000$유로인 케이블이 정확히 $K$개가 되도록 가격표를 정할 수 있는가? 그리고 모든 임차인이 정확히 같은 케이블 집합을 임대한다고 보장할 수 있는가?

형식적으로, 프로그램은 다음 두 종류의 질의를 처리해야 한다.

• 도시 $U$와 $V$가 주어진다. IOI가 $U$와 $V$ 사이에 새 케이블을 설치한다.
• $K$가 주어진다. 위 조건을 만족하도록 가격표를 정할 수 있는지 판정한다.

처음에는 케이블이 없다. 두 번째 종류의 질의는 IOI가 설치한 케이블로 모든 도시가 직접 또는 간접으로 연결된 뒤에만 주어진다고 가정해도 된다. IOI는 이미 케이블이 있는 두 도시 사이에 케이블을 다시 설치하지 않는다고 가정해도 된다.

첫 줄에 공백으로 구분된 정수 $N$과 $Q$가 주어진다 ($1 \le N \le 3 \cdot 10^5$, $1 \le Q \le 4 \cdot 10^5$). 각각 도시의 수와 질의의 수이다.

이어지는 $Q$개의 줄은 질의를 나타낸다. 첫 번째 종류의 질의는 '+ $U$ $V$' 형식이다 ($1 \le U \le N$, $1 \le V \le N$, $U \ne V$). 두 번째 종류의 질의는 '? $K$' 형식이다 ($0 \le K \le M$, 여기서 $M$은 그 시점까지 설치된 케이블의 수이다).

두 번째 종류의 질의마다 답을 한 줄에 출력한다. 가격표를 정할 수 있으면 'JAH'를, 그렇지 않으면 'EI'를 출력한다.