Tom is designing a menu system for a test editor. The menu consists of some menuitems, and each menuitem may contain some sub-menuitems (a sub-menuitem is also a menuitem) recursively, e.g., menuitem "File" may contain sub-menuitems "Open", "Save", "Save As", "Recent Files", "Send" and "Exit", and "Recent Files" may contain "Setting File", "Send" may contain "Mail" and "Fax". A menuitem may contain several words, and it is confirmed that the first letter in each word is a capital letter, and that the other letters are all small letters.
Each menuitem is associated with a hotkey, the menu is easier to use if the hotkeys are easier to remember. So Tom wants that the hotkey can only be a capital letter in a menuitem, which means the first letter in each word. Take "Save As" for example, the hotkey can only be 'S' or 'A'. It is clear that sub-menuitems of a menuitem can't be associated with the same hotkey, e.g., "Save" and "Save As" can't both use hotkey 'S', because they are both sub-menuitems of menu "File".
Since Tom believes press the same key twice is not convenient, he requests that the hotkeys of a menuitem and its sub-menuitems can't duplicate. In the previous example, "File" and "Recent Files" can't use the same hotkey 'F'. But this rule just affects the menuitem and its direct sub-menuitem, so "File" and "Setting File" can use the same hotkey 'F'.
Given a menu description, Tom wants to know whether it is possible to assign a hotkey for each menuitem or not.