Forest Verification

You are given an undirected graph with N nodes and M edges. Your task is to determine whether this graph forms a valid forest, i.e. a collection of disjoint trees.

A tree is an acyclic connected graph and a forest is a disjoint union of trees. A necessary property of a forest is that if there are c connected components, then the total number of edges is exactly N - c, which is always less than N.

Note: The nodes are numbered from 1 through N. The graph may be disconnected. If the graph contains any cycle then it is not a forest.

The input is provided through standard input (stdin) and the output must be printed using standard output (stdout).

Mathematical Formulation:
A graph is a forest if and only if it satisfies the following conditions: \[ M < N \quad \text{and for each connected component } C, \ |C| - 1 \text{ edges exist in } C. \]

inputFormat

The first line contains two integers N and M, where N is the number of nodes and M is the number of edges.

The following M lines each contain two integers u and v denoting an undirected edge between nodes u and v.

outputFormat

Print a single line: "FOREST" if the graph is a valid forest, otherwise "NOT A FOREST".

4 2
1 2
3 4

FOREST