시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 8 8 8 100.000%

문제

One of the most important data structures in computer science is the tree. You already dealt with binary trees in the qualification round. This problem is about general trees.

Trees are the subset of graphs that have the following 3 properties:

  1. A graph (a set of N nodes and M edges) is a tree when it is connected: for every node you can reach every other node following edges.
  2. A graph is not a tree if an edge is removed and the graph is no longer connected. That is, some nodes cannot be reached anymore.
  3. A graph is not a tree if, when an edge is added between two existing nodes A and B, a cycle is created. There is a cycle if there is more than one way to go from A to B.

You task is to decide if a given graph is a tree or not.

입력

The first line will contain an integer T representing the number of graphs to check. There will be at most 10 graphs in each test case.

Each of the graph will be represented as follows:

The first line will contain an integer N with the number of nodes in the graph. The number of nodes will be between 1 and 1000. The identifier of each node will be an integer from 1 to N. 

The next line will contain an integer M with the number of edges in the graph. There will be at most 106 edges.

The next M lines will contain 2 integers A and B each. These are the two nodes connected by an edge.

출력

For each graph, a single line with “tree” if the graph represents a tree or “graph“ otherwise.

예제 입력

2
4
3
2 1
3 4
1 3
3
3
1 2
1 2
3 2

예제 출력

tree
graph

예제 입력 2

2
7
5
7 2
2 4
4 3
5 6
6 1
7
6
7 2
2 4
4 3
4 5
6 5
1 6

예제 출력 2

graph
tree

힌트