# Check Mirror in N-ary Tree

Given two n-ary trees, the task is to check if they are mirrors of each other or not.

**Note:** you may assume that root of both the given tree as 1.

**Input:**

The first line of input contains an integer *T* denoting the no of test cases. Then *T* test cases follow. The first line of each test case contains two space-separated values *N* and *M* denoting the no. of nodes and edges respectively. Then in the next line, two lines are *2*M* space-separated values *u*, *v* denoting an edge from *u* to *v* for both trees.

**Output:**

For each test case in a new line print "YES" if both the trees are mirrors of each other else print "NO".

**Examples:**

INPUT:
T=1
N=3,M=3
1 2 1 3 2 4
1 3 1 2 2 4
OUTPUT:
YES
1 1
/ \ / \
2 3 3 2
/ \
4 4
Since they are mirror of each other.
INPUT:
T=1
N=4,M=4
1 2 1 3 2 4 2 5
1 3 1 2 2 4 2 5
OUTPUT:
NO
1 1
/ \ / \
2 3 3 2
/ \ / \
4 5 4 5
Here,
node 4 and 5 are not as in mirror so the tree is not mirror.

We will use stack and queue data structure since stack follow LIFO that is last in first out the way and queue follow FIFO first in first out pattern, is the trees are mirror then the top of the stack will be equal to the front of the queue and if they aren't equal it means that they are not the mirror of each other.

We will follow this approach, taking each node at a time and checking its connected component in stack and queue. For checking whether each subtree in itself is a mirror or not we will use a boolean variable flag, initially, the flag is true and each time we check if the top of stack and queue front are equal or not, if not then simply return NO as the answer and after checking all nodes return true if all are valid nodes.

C++ Implementation:Output:O(n*n)O(n)