You are tasked with writing a Java class named Menu to implement an infinitely deep menu. The menu consists of various options and prompts the user to select an option from the menu. Some menu options lead to submenus. The initial menu is referred to as the root menu. The class has a non$-$static method called run for starting to show the menu.

For each submenu $($excluding the root menu$),$ it contains $2$ to $7$ options, along with a "Back" option and an "Exit" option. The root menu contains n$+1$ options, where n is an input argument to the constructor of the Menu class. The first n options are for navigating to submenus, and the additional option $($the n$+1-$th option$)$ is the "Exit" option. Please note that the root menu does not include a "Back" option.

Typically, the entire menu structure would be defined in text files. However, for this bonus exercise, we will simply randomly set a number of options $($ranging from $2$ to $7)$ that lead to a submenu. When the user selects an option to navigate to a submenu that has not been visited before, the program should generate the submenu with a random number of navigation options $(2$ to $7),$ along with the "Back" and "Exit" options.

If the user navigates to a submenu that has been visited before, the program should display the same submenu again without regenerating it$.$ In other words, the submenu should be displayed again with the same number of options as before.

When the "Back" option is selected, the program should navigate back to the parent menu. If the "Exit" option is selected, the program should terminate and display the message "Goodbye!".

Your submission cannot include any loops. In other words, you must complete this task using recursion.

An example MenuDemo.java file is provided for testing purposes. You are not required to submit the MenuDemo.java file. I will test your Menu class with my own MenuDemo.java file.

Below are some example outputs that demonstrate the desired format, including menu indices and flow. Your program must be compatible with similar inputs. The red rectangles highlight the user input. The red texts provide further explanations.

$1$

IS$5311$ JAVA Programming for Business Applications Bonus $04$

Display the root menu initially.

Navigated to menu $2$ from the root menu.

Navigated to menu $2\mathrm{.}3$ from menu $2.$

Navigated to menu $2\mathrm{.}3\mathrm{.}5$ from menu $2\mathrm{.}3.$

Navigated BACK to menu $2\mathrm{.}3$ from menu $2\mathrm{.}3\mathrm{.}5.$ Note that the number of menu options must be the same as menu $2\mathrm{.}3$ above.

Navigated BACK to menu $2$ from menu $2\mathrm{.}3.$ Note that the number of menu options must be the same as menu $2$ above.

Navigated BACK to the root menu from menu $2.$ Similarly, the number of menu options must be the same as the root menu above.

Navigated to menu $2$ again from the root menu. The number of menu options must be the same as the menu $2$ above.

Navigated to menu $2\mathrm{.}3$ again from the menu $2.$ The number of menu options must be the same as the menu $2\mathrm{.}3$ above.

$2$

IS$5311$ JAVA Programming for Business Applications Bonus $04$

The bonus points will not be awarded if any outcome fails to meet the requirements. Below are some $($but not all$)$ common incorrect outcomes:

$1.$ Incertainsituations,themessage"Goodbye!"isnotdisplayedwhenthe program exits.

$2.$ Incertainsituations,themessage"Goodbye!"isdisplayedmorethanonce when the program exits.

$3.$ Therootmenuincludesa"Back"option.

$4.$ The"Back"optionismissinginsomesubmenus.

$5.$ Theindicesofoptionsinthesubmenusareincorrect.

$---------------------$

the content of Java class named "MenuDemo" is below:

public class MenuDemo $\{$

public static void main$($String$[]$ args$)\{$

Menu menu $=$ new Menu$(3)$;

menu.run$()$;

$\}$

$\}$