Manage E-commerce Category Hierarchies

This problem involves managing an e-commerce platform's category hierarchies. You are given a set of category relationships where each relationship consists of a subcategory and its immediate parent category. Some parent categories might not appear as a subcategory in any relationship.

Your task is to process queries of two types:

• FIND_SUBCATEGORIES <category>: Print all immediate subcategories of the given category, sorted in lexicographical order. If the category has no subcategories, print an empty line.
• FIND_PARENT <category>: Print the parent of the given category. If the specified category does not have a recorded parent, print \(\text{None}\).

Note: The output for each query should be printed on a separate line.

inputFormat

The input is given via stdin in the following format:

1. The first line contains two space-separated integers: T and R, where T is the total number of categories (including those that only appear as parent) and R is the number of category relationships provided.
2. The next R lines each contain two strings representing a subcategory and its parent category.
3. The following line contains an integer Q, the number of queries.
4. The next Q lines each contain a query in one of the following formats:
   • FIND_SUBCATEGORIES <category>
   • FIND_PARENT <category>

outputFormat

For each query, output the result on a new line. For a FIND_SUBCATEGORIES query, output all immediate subcategories of the given category (if any) in lexicographical order separated by a single space. For a FIND_PARENT query, output the parent category, or None if it does not exist.

## sample

7 6
laptops electronics
mobiles electronics
clothing fashion
men clothing
women clothing
accessories fashion
4
FIND_SUBCATEGORIES electronics
FIND_SUBCATEGORIES clothing
FIND_PARENT laptops
FIND_PARENT fashion

laptops mobiles
men women
electronics
None

</p>