Network Cycle Detection

You are given an undirected network consisting of n nodes and m links. Each link connects two nodes, and the network can be disconnected. Your task is to determine whether the network is Faulty or Functional. The network is considered Faulty if there exists at least one communication ring, i.e. a cycle, anywhere in the network; otherwise, the network is Functional.

You can solve this problem by performing a Depth-First Search (DFS) on each connected component of the network. During the DFS, if you encounter a node that has already been visited and is not the parent of the current node, a cycle exists. In mathematical terms, if the graph contains a cycle, it is faulty. The cycle detection condition can be written in \(\LaTeX\) as follows:

[ \exists, v, u \text{ such that } (v, u) \in E \text{ and } u \neq parent(v) \text{ where } visited(u)=true ]

If no such condition is met for all components of the network, then the network is functional.

inputFormat

The first line of the input contains two integers n and m where:

• n is the number of nodes.
• m is the number of links.

The next m lines each contain two integers a and b indicating that there is a link between node a and node b (1-indexed).

outputFormat

Output a single word:

• Faulty if the network contains at least one cycle.
• Functional if the network does not have any cycles.

## sample

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

Faulty

</p>