Given two n-ary trees. Check if they are mirror images of each other or not. You are also given e denoting the number of edges in both trees, and two arrays, A[] and B[].  Each array has 2*e space separated values u,v denoting an edge from u to v for the both trees.
Example 1:
Input:
n = 3, e = 2
A[] = {1, 2, 1, 3}
B[] = {1, 3, 1, 2}
Output:
1
Explanation:
   1          1
 / \        /  \
2   3      3    2 
As we can clearly see, the second tree
is mirror image of the first.
Example 2:
Input:
n = 3, e = 2
A[] = {1, 2, 1, 3}
B[] = {1, 2, 1, 3}
Output:
0
Explanation:
   1          1
 / \        /  \
2   3      2    3 
As we can clearly see, the second tree
isn't mirror image of the first.
Your Task:
You don't need to read input or print anything. Your task is to complete the function checkMirrorTree() which takes 2 Integers n, and e;  and two arrays A[] and B[] of size 2*e as input and returns 1 if the trees are mirror images of each other and 0 if not.
Expected Time Complexity: O(e)
Expected Auxiliary Space: O(e)
Constraints:
1 <= n,e <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: class Solution:

    def checkMirrorTree(self, n, e, A, B):

        # code here

Solutions:
from collections import defaultdict

class Solution:

	def checkMirrorTree(self, n, e, A, B):
		d = defaultdict(list)
		for i in range(0, 2 * e, 2):
			d[A[i]].append(A[i + 1])
		for i in range(0, 2 * e, 2):
			if B[i] not in d:
				return 0
			elif B[i + 1] != d[B[i]].pop():
				return 0
		return 1


class Solution:

	def checkMirrorTree(self, n, e, A, B):
		m = {}
		for i in range(0, 2 * e, 2):
			if A[i] in m:
				m[A[i]].append(A[i + 1])
			else:
				m[A[i]] = [A[i + 1]]
		for i in range(0, 2 * e, 2):
			if B[i + 1] != m[B[i]].pop():
				return 0
		return 1


class Solution:

	def checkMirrorTree(self, n, e, A, B):
		dictA = {}
		dictB = {}
		for x in range(0, 2 * e, 2):
			if A[x] in dictA:
				dictA[A[x]].append(A[x + 1])
			else:
				dictA[A[x]] = [A[x + 1]]
			if B[x] in dictB:
				dictB[B[x]].append(B[x + 1])
			else:
				dictB[B[x]] = [B[x + 1]]
		for x in dictA:
			if dictA[x] != list(reversed(dictB[x])):
				return 0
		return 1


class Solution:

	def checkMirrorTree(self, n, e, A, B):
		i = 0
		mp = {}
		if len(A) != len(B):
			return 0
		while i < len(A):
			try:
				mp[A[i]].append(A[i + 1])
			except:
				mp[A[i]] = [A[i + 1]]
			i = i + 2
		j = 0
		while j < len(B):
			if B[j] not in mp.keys() or len(mp[B[j]]) == 0 or mp[B[j]].pop() != B[j + 1]:
				return 0
			j = j + 2
		return 1


from collections import defaultdict as dict

class Solution:

	def checkMirrorTree(self, n, e, A, B):
		mp = dict(list)
		for i in range(0, 2 * e, 2):
			u = A[i]
			v = A[i + 1]
			mp[u].append(v)
		for i in range(0, 2 * e, 2):
			u = B[i]
			v = B[i + 1]
			if u in mp and mp[u] != []:
				if mp[u][-1] == v:
					mp[u].pop(-1)
				else:
					return 0
			else:
				return 0
		return 1


from collections import deque

class Solution:

	def checkMirrorTree(self, n, e, A, B):
		s = []
		q = []
		for i in range(n + 1):
			s.append([])
			queue = []
			q.append(queue)
		for i in range(0, 2 * e, 2):
			s[A[i]].append(A[i + 1])
			q[B[i]].append(B[i + 1])
		for i in range(1, n + 1):
			while len(s[i]) > 0 and len(q[i]) > 0:
				a = s[i][len(s[i]) - 1]
				s[i].pop()
				b = q[i][0]
				q[i].pop(0)
				if a != b:
					return 0
		return 1


class Solution:

	def checkMirrorTree(self, n, e, A, B):
		dic = {}
		for i in range(0, len(A), 2):
			if A[i] not in dic:
				dic[A[i]] = []
			dic[A[i]].append(A[i + 1])
		for i in range(0, len(B), 2):
			if B[i] not in dic:
				return 0
			else:
				if dic[B[i]][-1] != B[i + 1]:
					return 0
				dic[B[i]].pop()
		for i in dic:
			if dic[i]:
				return 0
		return 1


class Solution:

	def checkMirrorTree(self, n, e, A, B):
		a1 = {}
		a2 = {}
		a = []
		b = []
		d = A[0]
		f = B[0]
		for i in range(0, len(A) - 1, 2):
			if A[i] in a1.keys():
				a1[A[i]].append(A[i + 1])
			else:
				a1[A[i]] = [A[i + 1]]
			if B[i] in a2.keys():
				a2[B[i]].append(B[i + 1])
			else:
				a2[B[i]] = [B[i + 1]]
		f = 0
		if sorted(a1.keys()) == sorted(a2.keys()):
			for k in a1.keys():
				if a1[k] != a2[k][::-1]:
					f = 1
					return 0
		else:
			return 0
		if f == 0:
			return 1


class Solution:

	def checkMirrorTree(self, n, e, A, B):
		adjListA = [[] for i in range(n)]
		adjListB = [[] for i in range(n)]
		for i in range(0, 2 * e, 2):
			(x, y) = (A[i], A[i + 1])
			(a, b) = (B[i], B[i + 1])
			adjListA[x].append(y)
			adjListB[a].append(b)
		for (i, x) in enumerate(adjListA):
			if adjListA[i][::-1] != adjListB[i]:
				return 0
		return 1


class Solution:

	def checkMirrorTree(self, n, e, A, B):
		dp1 = [[] for i in range(n)]
		dp2 = [[] for i in range(n)]
		i = 0
		while i < len(A):
			dp1[A[i] - 1].append(A[i + 1] - 1)
			dp2[B[i] - 1].append(B[i + 1] - 1)
			i += 2
		for i in dp2:
			i.reverse()
		for i in range(n):
			if dp1[i] != dp2[i]:
				return 0
		return 1


class Solution:

	def checkMirrorTree(self, n, e, A, B):
		hashmap = {}
		for i in range(0, 2 * e, 2):
			if A[i] not in hashmap:
				hashmap[A[i]] = [A[i + 1]]
			else:
				hashmap[A[i]].append(A[i + 1])
		for i in range(0, 2 * e, 2):
			if B[i] not in hashmap:
				return 0
			elif B[i + 1] != hashmap[B[i]].pop():
				return 0
		return 1


class Solution:

	def checkMirrorTree(self, n, e, arr_1, arr_2):
		n = len(arr_1)
		m = len(arr_2)
		if n != m:
			return False
		node_element_dict = {}
		n = len(arr_1)
		i = 0
		while i < n:
			node = arr_1[i]
			connect_to = arr_1[i + 1]
			if node in node_element_dict:
				node_element_dict[node].append(connect_to)
			else:
				node_element_dict[node] = [connect_to]
			i = i + 2
		m = len(arr_2)
		j = 0
		answer = 1
		while j < m:
			node = arr_2[j]
			connect_to = arr_2[j + 1]
			if node not in node_element_dict:
				answer = 0
				break
			else:
				pop_element = node_element_dict[node].pop()
				if pop_element != connect_to:
					answer = 0
					break
			j = j + 2
		return answer


class Solution:

	def checkMirrorTree(self, n, e, A, B):
		map1 = {}
		i = 0
		while i < 2 * e:
			if A[i] in map1:
				map1[A[i]] += [A[i + 1]]
			else:
				map1[A[i]] = [A[i + 1]]
			i += 2
		j = 0
		while j < 2 * e:
			if map1[B[j]][-1] != B[j + 1]:
				return 0
			map1[B[j]].pop()
			j += 2
		return 1


class Solution:

	def checkMirrorTree(self, n, e, A, B):
		(s1, s2) = ([], [])
		for i in range(n + 1):
			s1.append([])
			s2.append([])
		for i in range(0, 2 * e, 2):
			s1[A[i]].append(A[i + 1])
			s2[B[i]].append(B[i + 1])
		for i in range(1, n + 1):
			while len(s1[i]) > 0 and len(s2[i]) > 0:
				a = s1[i][len(s1[i]) - 1]
				s1[i].pop()
				b = s2[i][0]
				s2[i].pop(0)
				if a != b:
					return 0
		return 1


class Solution:

	def constructMap(self, n, lst, dct):
		mapA = dct
		i = 0
		j = 1
		while i <= n and j <= n:
			try:
				mapA[lst[i]] = mapA[lst[i]] + [lst[j]]
			except:
				mapA[lst[i]] = [lst[j]]
			i += 2
			j += 2
		return mapA

	def checkMirrorTree(self, n, e, A, B):
		mapA = {}
		mapB = {}
		mapA = self.constructMap(2 * e, A, mapA)
		mapB = self.constructMap(2 * e, B, mapB)
		for itr in mapA:
			tA = mapA.get(itr)
			tB = mapB.get(itr)
			if tA[::-1] != tB:
				return 0
		return 1


class Solution:

	def checkMirrorTree(self, n, e, A, B):
		mpa = dict()
		mpb = dict()
		for i in range(1, n + 1):
			mpa[i] = []
			mpb[i] = []
		for i in range(0, 2 * e, 2):
			mpa[A[i]].append(A[i + 1])
			mpb[B[i]].append(B[i + 1])
		for i in range(1, n + 1):
			lista = mpa[i]
			listb = mpb[i]
			flag = True
			if len(lista) != len(listb):
				flag = False
				return 0
			else:
				ln = len(lista)
				for x in range(ln):
					if lista[x] != listb[ln - 1 - x]:
						flag = False
						return 0
		return 1


class Solution:

	def checkMirrorTree(self, n, e, A, B):
		c = {}
		for i in range(0, 2 * e, 2):
			if A[i] not in c:
				c[A[i]] = [A[i + 1]]
			else:
				c[A[i]].append(A[i + 1])
		for i in range(0, 2 * e, 2):
			if B[i] in c and c[B[i]] and (c[B[i]].pop() == B[i + 1]):
				continue
			else:
				return 0
		return 1


from collections import defaultdict as dd

class Solution:

	def checkMirrorTree(self, n, e, A, B):
		A_edges = dd(lambda : [])
		B_edges = dd(lambda : [])
		for i in range(0, 2 * e, 2):
			A_edges[A[i]].append(A[i + 1])
			B_edges[B[i]].append(B[i + 1])
		if len(A) != len(B):
			return 0
		for item in A_edges:
			if A_edges[item] != B_edges[item][::-1]:
				return 0
		return 1


class Solution:

	def checkMirrorTree(self, n, e, A, B):
		h1 = {}
		h2 = {}
		prevpar = None
		for i in range(e):
			par = A[2 * i]
			if par not in h1:
				h1[par] = []
			h1[par].append(A[2 * i + 1])
		for i in range(e):
			par = B[2 * i]
			if par not in h2:
				h2[par] = []
			h2[par].append(B[2 * i + 1])
		root = A[0]

		def ismir(root, h1, h2):
			if root not in h1:
				return 1
			nnn = len(h1[root])
			for i in range(nnn):
				if h1[root][i] == h2[root][nnn - i - 1]:
					if not ismir(h1[root][i], h1, h2):
						return 0
				else:
					return 0
			return 1
		return ismir(root, h1, h2)


class Solution:

	def checkMirrorTree(self, n, e, A, B):
		mp = dict()
		i = 0
		while i < len(A):
			if A[i] in mp:
				mp[A[i]].append(A[i + 1])
			else:
				mp[A[i]] = []
				mp[A[i]].append(A[i + 1])
			i += 2
		i = 0
		while i < len(B):
			if B[i] in mp and len(mp[B[i]]) > 0:
				if mp[B[i]][-1] == B[i + 1]:
					mp[B[i]].pop()
				else:
					return 0
			i += 2
		return 1


from collections import defaultdict

class Solution:

	def checkMirrorTree(self, n, e, A, B):
		check_mirror = defaultdict(list)
		for i in range(0, 2 * e, 2):
			check_mirror[A[i]].append(A[i + 1])
		for i in range(0, 2 * e, 2):
			if check_mirror[B[i]][-1] == B[i + 1]:
				check_mirror[B[i]].pop()
			else:
				return 0
		return 1


class Solution:

	def checkMirrorTree(self, n, e, A, B):
		a1 = {}
		a2 = {}
		for i in range(1, n + 1):
			a1[i] = []
			a2[i] = []
		for i in range(0, len(A), 2):
			if A[i] not in a1:
				a1[A[i]] = []
			a1[A[i]].append(A[i + 1])
		for i in range(0, len(B), 2):
			if B[i] not in a2:
				a2[B[i]] = []
			a2[B[i]].append(B[i + 1])
		for i in a1:
			if a1[i] != a2[i][::-1]:
				return 0
		return 1


class Solution:

	def __init__(self):
		self.flag = 1

	def dfs(self, a1, a2, g):
		if g not in a2 or a1[g] != a2[g][::-1]:
			self.flag = 0
			return
		else:
			print(a1[g], a2[g])
		for i in a1[g]:
			self.dfs(a1, a2, i)

	def checkMirrorTree(self, n, e, A, B):
		a1 = {}
		a2 = {}
		for i in range(1, n + 1):
			a1[i] = []
			a2[i] = []
		for i in range(0, len(A), 2):
			if A[i] not in a1:
				a1[A[i]] = []
			a1[A[i]].append(A[i + 1])
		for i in range(0, len(B), 2):
			if B[i] not in a2:
				a2[B[i]] = []
			a2[B[i]].append(B[i + 1])
		for i in a1:
			if a1[i] != a2[i][::-1]:
				return 0
		return 1


class Solution:

	def checkMirrorTree(self, n, e, A, B):
		d = {}
		for i in range(0, 2 * e, 2):
			d[A[i]] = d.get(A[i], []) + [A[i + 1]]
		for i in range(0, 2 * e, 2):
			if B[i + 1] != d[B[i]].pop():
				return 0
		return 1


class Solution:

	def checkMirrorTree(self, n, e, A, B):
		dic1 = {}
		for i in range(0, len(A), 2):
			if A[i] not in dic1:
				dic1[A[i]] = [A[i + 1]]
			else:
				dic1[A[i]].append(A[i + 1])
		dic2 = {}
		for i in range(0, len(B), 2):
			if B[i] not in dic2:
				dic2[B[i]] = [B[i + 1]]
			else:
				dic2[B[i]].append(B[i + 1])
		for i in dic1:
			if dic1[i] != dic2[i][::-1]:
				return 0
		return 1


from collections import defaultdict

class Solution:

	def checkMirrorTree(self, n, e, A, B):
		a1 = defaultdict(list)
		a2 = defaultdict(list)
		for (i, (p1, p2)) in enumerate(zip(A[::2], B[::2])):
			c = 2 * i + 1
			a1[p1].append(A[c])
			a2[p2].append(B[c])
		for k in a1.keys():
			if k in a2:
				if a1[k] != a2[k][::-1]:
					return 0
			else:
				return 0
		return 1


from collections import defaultdict

class Solution:

	def checkMirrorTree(self, n, e, A, B):
		i = 0
		d = defaultdict(list)
		while i < 2 * e:
			d[A[i]].append(A[i + 1])
			i += 2
		j = 0
		while j < 2 * e:
			x = d[B[j]].pop()
			if x != B[j + 1]:
				return 0
			j += 2
		return 1


class Solution:

	def checkMirrorTree(self, n, e, A, B):
		has = {}
		for i in range(1, n + 1):
			has[i] = []
		for i in range(0, 2 * e, 2):
			has[A[i]].append(A[i + 1])
		for i in range(0, 2 * e, 2):
			temp = has[B[i]].pop()
			if temp != B[i + 1]:
				return 0
		return 1


class Solution:

	def checkMirrorTree(self, n, e, A, B):
		d = {}
		for i in range(0, len(A), 2):
			if A[i] not in d:
				d[A[i]] = []
			d[A[i]].append(A[i + 1])
		for i in range(0, len(B), 2):
			k = d[B[i]].pop()
			if k != B[i + 1]:
				return 0
		return 1


class Solution:

	def checkMirrorTree(self, n, e, A, B):
		d = {}
		for i in range(0, len(A), 2):
			if A[i] in d:
				d[A[i]].append(A[i + 1])
			else:
				d[A[i]] = [A[i + 1]]
		e = {}
		for i in range(0, len(B), 2):
			if B[i] in e:
				e[B[i]].append(B[i + 1])
			else:
				e[B[i]] = [B[i + 1]]
		for i in d:
			if i not in e:
				return 0
			t1 = d[i]
			t2 = e[i][::-1]
			if t1 != t2:
				return 0
		return 1


class Solution:

	def checkMirrorTree(self, n, edges, array1, array2):
		map = {}
		for i in range(0, edges * 2, 2):
			if array1[i] in map:
				map[array1[i]].append(array1[i + 1])
			else:
				map[array1[i]] = [array1[i + 1]]
		for i in range(0, edges * 2, 2):
			if map[array2[i]].pop() != array2[i + 1]:
				return 0
		return 1


class Solution:

	def checkMirrorTree(self, n, e, a, b):
		m = {}
		for i in range(0, 2 * e, 2):
			if a[i] in m:
				m[a[i]].append(a[i + 1])
			else:
				m[a[i]] = [a[i + 1]]
		for i in range(0, 2 * e, 2):
			if m[b[i]].pop() != b[i + 1]:
				return 0
		return 1


from collections import defaultdict

class Solution:

	def checkMirrorTree(self, n, e, A, B):
		d1 = defaultdict(list)
		d2 = defaultdict(list)
		for i in range(0, 2 * e, 2):
			d1[A[i]].append(A[i + 1])
			d2[B[i]].append(B[i + 1])
		for i in d1:
			d2[i] = d2[i][::-1]
			if d1[i] != d2[i]:
				return 0
		return 1


import collections

class Solution:

	def checkMirrorTree(self, n, e, A, B):
		g1 = collections.defaultdict(list)
		g2 = collections.defaultdict(list)
		for i in range(0, 2 * e, 2):
			g1[A[i]].append(A[i + 1])
			g2[B[i]].append(B[i + 1])
		return +self.dfs(1, 1, g1, g2)

	def dfs(self, n1, n2, g1, g2):
		if n1 != n2:
			return False
		for (nei1, nei2) in zip(g1[n1], reversed(g2[n2])):
			if not self.dfs(nei1, nei2, g1, g2):
				return False
		return True


class Solution:

	def checkMirrorTree(self, n, e, A, B):
		map1 = {}
		i = 0
		temp = A[0]
		ans = []
		while i < len(A) - 1:
			if A[i] == temp:
				ans.append(A[i + 1])
				i += 2
			else:
				map1[temp] = ans
				ans = []
				temp = A[i]
		map1[temp] = ans
		i = 0
		while i < len(B) - 1:
			if B[i + 1] != map1[B[i]].pop():
				return 0
			i += 2
		return 1


class Solution:

	def checkMirrorTree(self, n, e, A, B):
		from collections import defaultdict
		list1 = defaultdict(list)
		list2 = defaultdict(list)
		for i in range(0, 2 * e - 1, 2):
			list1[A[i]].append(A[i + 1])
			list2[B[i]].append(B[i + 1])

		def dfs(n1, n2, list1, list2):
			if n1 != n2:
				return 0
			for (nei1, nei2) in zip(list1[n1], list2[n2][::-1]):
				if not dfs(nei1, nei2, list1, list2):
					return 0
			return 1
		return dfs(1, 1, list1, list2)


import collections

class Solution:

	def checkMirrorTree(self, n, e, A, B):
		g1 = collections.defaultdict(list)
		g2 = collections.defaultdict(list)
		for i in range(0, 2 * e, 2):
			g1[A[i]].append(A[i + 1])
			g2[B[i]].append(B[i + 1])
		for i in g1:
			if i not in g2:
				return 0
			elif g1[i] != g2[i][::-1]:
				return 0
		return 1


class Solution:

	def checkMirrorTree(self, n, e, A, B):
		map = dict()
		for i in range(n):
			map[i] = []
		for i in range(0, 2 * e, 2):
			map[A[i]].append(A[i + 1])
		for i in range(0, 2 * e, 2):
			if len(map[B[i]]) == 0 or B[i + 1] != map[B[i]].pop():
				return 0
		return 1


class Solution:

	def checkMirrorTree(self, n, e, A, B):

		def _buildTree(arr):
			n = len(arr)
			graph = {}
			for i in range(0, n, 2):
				if arr[i] not in graph:
					graph[arr[i]] = []
				graph[arr[i]].append(arr[i + 1])
			return graph
		tree1 = _buildTree(A)
		tree2 = _buildTree(B)

		def _isMirror(root1, root2):
			if root1 != root2:
				return False
			children1 = tree1.get(root1, [])
			children2 = tree2.get(root2, [])
			if len(children1) != len(children2):
				return False
			n = len(children1)
			for i in range(n):
				if _isMirror(children1[i], children2[n - i - 1]) == False:
					return False
			return True
		return 1 if _isMirror(A[0], B[0]) else 0


from collections import defaultdict

class Solution:

	def checkMirrorTree(self, n, e, A, B):
		d = {}
		rd = {}
		for i in range(1, n + 1):
			d[i] = []
			rd[i] = []
		for i in range(0, len(A) - 1, 2):
			d[A[i]].append(A[i + 1])
			rd[B[i]].append(B[i + 1])
		res = []
		for i in range(1, n + 1):
			d[i].reverse()
		if d == rd:
			return 1
		else:
			return 0


class Solution:

	def checkMirrorTree(self, n, e, A, B):
		(set1, set2) = ({}, {})
		for i in range(0, len(A), 2):
			if A[i:i + 2][0] not in set1:
				set1[A[i:i + 1][0]] = []
			set1[A[i:i + 2][0]].append(A[i:i + 2][1])
		for i in range(0, len(B), 2):
			if B[i:i + 2][0] not in set2:
				set2[B[i:i + 1][0]] = []
			set2[B[i:i + 2][0]].append(B[i:i + 2][1])
		for i in set1.keys():
			if set1[i][::-1] != set2[i]:
				return 0
		return 1


class Solution:

	def checkMirrorTree(self, n, e, A, B):
		dic = {}
		for i in range(0, len(A), 2):
			try:
				dic[A[i]].append(A[i + 1])
			except KeyError:
				dic[A[i]] = []
				dic[A[i]].append(A[i + 1])
		for i in range(0, len(B), 2):
			if B[i] in dic.keys() and len(dic[B[i]]) > 0:
				el = dic[B[i]].pop(-1)
				if el != B[i + 1]:
					return 0
			else:
				return 0
		return 1


class Solution:

	def checkMirrorTree(self, n, e, A, B):
		mp = {}
		for i in range(e):
			u = A[2 * i]
			v = A[2 * i + 1]
			if u in mp:
				mp[u].append(v)
			else:
				mp[u] = [v]
		for i in range(e):
			u = B[2 * i]
			v = B[2 * i + 1]
			if u not in mp:
				return 0
			if len(mp[u]) == 0:
				return 0
			top = mp[u].pop()
			if v != top:
				return 0
		return 1


class Solution:

	def checkMirrorTree(self, n, e, A, B):
		if A == B and len(A) > 2:
			temp = set(A)
			length = len(temp)
			flag = 0
			s = A.count(A[0]) + A.count(A[-1])
			if s == 2:
				for i in range(1, length - 1):
					if A.count(A[i]) != 2:
						return 0
				return 1
			else:
				return 0
		return 1


class Solution:

	def checkMirrorTree(self, n, e, A, B):
		(dic, bic) = ({}, {})
		for i in range(0, len(A), 2):
			try:
				dic[A[i]] += [A[i + 1]]
			except:
				dic[A[i]] = [A[i + 1]]
		for i in range(0, len(B), 2):
			try:
				bic[B[i]] += [B[i + 1]]
			except:
				bic[B[i]] = [B[i + 1]]
		for i in dic:
			try:
				if dic[i] != bic[i][::-1]:
					return 0
			except:
				return 0
		return 1


from collections import defaultdict

class Solution:

	def getAdj(self, A):
		dc = defaultdict(list)
		i = 0
		while i < len(A):
			dc[A[i]].append(A[i + 1])
			i += 2
		return dc

	def solve(self, A, B, u, v):
		if u != v:
			return False
		if len(A[u]) != len(B[u]):
			return False
		n = len(A[u])
		i = 0
		j = n - 1
		ans = True
		while i < n:
			ans = ans and self.solve(A, B, A[u][i], B[u][j])
			i += 1
			j -= 1
		return ans

	def isTree(self, A, B):
		u = list(A.keys())[0]
		if u not in B.keys():
			return False
		return self.solve(A, B, u, u)

	def checkMirrorTree(self, n, e, A, B):
		adjA = self.getAdj(A)
		adjB = self.getAdj(B)
		return int(self.isTree(adjA, adjB))


class Solution:

	def checkMirrorTree(self, n, e, A, B):
		d1 = {}
		d2 = {}
		for i in range(0, 2 * e, 2):
			if A[i] not in d1:
				d1[A[i]] = [A[i + 1]]
			else:
				d1[A[i]].append(A[i + 1])
		for i in range(0, 2 * e, 2):
			if B[i] not in d2:
				d2[B[i]] = [B[i + 1]]
			else:
				d2[B[i]].append(B[i + 1])
		l = list(d1.keys())
		for i in l:
			t1 = d1[i]
			t2 = d2[i]
			t2.reverse()
			if t1 != t2:
				return 0
		return 1


class Solution:

	def checkMirrorTree(self, n, e, a, b):

		def checker(lst1, lst2):
			if len(lst1) != len(lst2):
				return False
			for i in range(len(lst1)):
				if lst1[i] != lst2[i]:
					return False
			return True
		from collections import defaultdict
		d1 = defaultdict(list)
		d2 = defaultdict(list)
		pointer = 0
		for i in range(e):
			d1[a[pointer]].append(a[pointer + 1])
			d2[b[pointer]].append(b[pointer + 1])
			pointer += 2
		queue1 = []
		queue1.append(a[0])
		queue2 = []
		queue2.append(b[0])
		while queue1 and queue2:
			if checker(queue1, queue2[::-1]) == False:
				return 0
			count = len(queue1)
			for i in range(count):
				curr1 = queue1.pop(0)
				curr2 = queue2.pop(0)
				for j in d1[curr1]:
					queue1.append(j)
				for j in d2[curr2]:
					queue2.append(j)
		if len(queue1) != len(queue2):
			return 0
		return 1