XML encoding

The eXtensible Markup Language (XML) is a simple text-based format for representing information. The syntax for XML is as follows:

1. Element => TAG Attributes END Child END
2. Attribute => TAG Value

• Value: String value.
• TAG: Default mapping to an integer value.
• Child: List of ‘Elements’ or a single ‘Value’. Never both.
• End: Encoded as 0.

You are given an ‘Element’ object and the mapping of each ‘TAG’ to an integer value. The task is to encode this ‘Element’ using the ‘TAG’ mapping and return the resultant string.

Example:

Element object:
<codingNinjas course=“InterviewPreparation” type=“IndividualCourse”>
    <topic name=“Aptitude”>CourseContents</topic>
</codingNinjas>

Tag mapping:
‘codingNinjas’ => 1, ‘topic’ => 2, ‘courseName’ => 3, ‘type’ => 4, ‘topicName’ => 5

The given element is ‘codingNinjas’, and it has a single child element ‘topic’. The element ‘codingNinjas’ has two attributes having tags as ‘course’ and ‘type’. The element ‘topic’ has one attribute with the tag as ‘name’. So, the encoded string is: 

‘1 3 InterviewPreparation 4 IndividualCourse 0 2 5 Aptitude 0 CourseContents 0 0’

Note:

1. ‘END’ is always encoded as 0.
2. An ‘Element’ can have zero or multiple ‘Attributes’.

Function description:

The function ‘encodeXML’ has the following parameters:
Pointer to an ‘Element’ object.
Mapping of ‘TAG’ name (string) to an integer value.
Structure of ‘Element’ and ‘Attribute’ object:
Element {
    String tag;
    List<Attribute> attributes;
    List<Element *> child;
    String value;
}
Attribute {
    String tag;
    String value;
}

If ‘Element’ stores a list of child elements, then ‘(Element => values)’ stores an empty string.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains an integer ‘N’ denoting the count of elements, including nested elements.

The following ‘N’ blocks of lines contain the description of ‘N’ elements. Each block is as follows:

 1. Each block’s first line contains three space-separated values, integer ‘ID’ denoting the element’s id, ‘M’ denoting the number of ‘Attributes’, and a string denoting the element’s ‘tag’. The ‘ID’ is used later on to identify the child elements.
 2. The next ‘M’ lines contain two space-separated integers denoting the ‘tag’ and ‘value’ of each ‘Attribute’.
 3. The next line contains either of the following:
     a. If the element stores a value, it contains the integer 0 and a string denoting the ‘value’ in the element, separated by space.
     b. Otherwise, an integer ‘C’ denoting the number of child elements.

The next ‘N - 1’ lines contain two space-separated integers, ‘A’ and ‘B’, the element with ‘id’ as ‘B’ is the child of the element with ‘id’ as ‘A’. The given ‘Element’ object always has ‘id’ equal to ‘1’ and has no parent.

The next line of each test case contains an integer ‘S’ denoting the number of ‘tags’.

The next ‘S’ lines of each test case contain two space-separated values, a string denoting the ‘tag’ name and an integer mapped to this ‘tag’.

Output format:

For each test case, return the encoded string.

Note:

You do not need to print anything; it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10
2 <= N <= 1000

The count of ‘Attributes’ of all elements doesn’t exceed 1000.
The string ‘Value’ is non-empty and contains only ‘a-z’ and ‘A-Z’ characters.

Time Limit: 1 sec