Bcy is playing Minecraft 1.10 and he is building a complicated circuit using redstone dust and repeaters and comparators and redstone blocks and all that good stuff to spice up his already high-tech virtual home. Yay. However, as any redstone Minecrafter would know, if bcy places 2 repeaters facing opposite directions, hooks them up with redstone wire and sends a redstone current through the circuit, it would result in an infinite loop and a 'forever-on' status!!!! Oh no!!!
bcy's circuit has suddenly messed up. He believes it is caused by an infinite repeater loop in his circuit that he must have accidentally triggered at some point in his redstone engineering. With all the pistons and intricate wiring in the way, bcy cannot solve the problem on his own. Being a C++ freak, you decided to help bcy out by coding a program to test if any infinite loops were present.
The first line of input contains 2 integers, ~N~ and ~E~, space-separated. ~N~ represents the number of redstone repeaters (conveniently labelled ~1 \dots N~) in bcy's circuit, while ~E~ represents the number of redstone wires hooked up to each repeater (can be related to the edges of a graph). The following ~E~ lines of input contain 2 integers, ~A~ and ~B~. These define a connection between repeater ~A~ and repeater ~B~. It is guaranteed that this defines a 1-directional connection where ~A~ points to ~B~ but not otherwise.
Output, on a single line,
Infinite Loop Present if only 1 infinite loop is present.
Infinite Loops Present if more than 1 infinite loop is present. If there are no infinite loops, output
No Infinite Loops.
Subtask 1 [100%]
~1 \le N \le 1000~
~1 \le E \le 1100~
Subtask 2 [0%]
Sample test cases.
Sample Input 1
4 4 1 2 2 4 1 3 4 4
Sample Output 1
Infinite Loop Present
According to the last line of input where repeater 4 is connected to itself. This means that an infinite loop is present as the redstone current would come out of repeater 4 and go back into itself. The graph can be visualized as follows:
As such, an infinite loop is present.
Sample Input 2
4 5 1 2 2 3 3 1 3 4 4 4
Sample Output 2
Infinite Loops Present
2 3, and
3 1 all create a triangle like loop. And the input
4 4 means repeater 4 is connected to itself. Thus there are 2 infinite loops and we output
Infinite Loops Present. The graph can be visualized as follows: