트리

트리는 다음 세 가지 성질을 만족하는 그래프다.

1. 연결되어 있다. 어느 정점에서 출발하든 간선을 따라 다른 모든 정점에 도달한다.
2. 간선을 하나 제거하면 연결이 끊어진다. 즉 더 이상 도달할 수 없는 정점이 생긴다.
3. 이미 있는 두 정점 A와 B 사이에 간선을 하나 추가하면 사이클이 생긴다. A에서 B로 가는 방법이 두 가지 이상이면 사이클이 있는 것이다.

그래프가 주어지면 트리인지 판정한다.

첫째 줄에 판정할 그래프의 개수 $T$가 주어진다. $T$는 10 이하다.

각 그래프는 다음 형식으로 주어진다.

첫째 줄에 정점의 개수 $N$이 주어진다. $1 \le N \le 1000$이고, 정점 번호는 1부터 $N$까지다.

다음 줄에 간선의 개수 $M$이 주어진다. $0 \le M \le 10^6$이다.

이어지는 $M$개 줄에는 간선이 잇는 두 정점 $A$와 $B$가 주어진다. $A$와 $B$는 같을 수 있고, 같은 쌍이 두 번 이상 나올 수 있다.

모든 그래프의 $M$을 합한 값은 $10^6$ 이하다.

각 그래프마다 한 줄에, 트리이면 tree를, 아니면 graph를 출력한다.