Determine whether an undirected graph is a tree.

Input

The first line contains n and m. The next m lines contain undirected edges.

• 1 <= n <= 1000

Output

Print 1 if the graph is connected and acyclic; otherwise, print 0.

Example

Input

5 4
1 2
1 3
3 4
3 5

Output

1