Given a 2d list that represents the nodes of a Binary tree with N nodes, the task is to find the maximum GCD of the siblings of this tree without actually constructing it.
Note: If there are no pairs of siblings in the given tree, print 0. Also, if given that there's an edge between a and b in the form of {a,b} in the list, then a is the parent node.
Example 1:
Input:
N = 7
arr = {{4, 5}, {4, 2}, {2, 3}, {2, 1}, {3, 6}, {3, 12}}
Output:
6
Explanation:
For the above tree, the maximum GCD
for the sibilings is 6, formed for the
nodes 6 and 12 for the children of node 3.
Example 2:
Input:
N = 3
arr[] = {{1,2}, {1,4}} 
Output :
2
Explanation:
For the above tree, the maximum GCD
for the sibilings is 2, formed for the
nodes 2 and 4 for the children of node 1.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function maxBinTreeGCD() which takes an integer N and a 2-d list denoting the edges as input and returns the maximum GCD of sibilings of the tree.
Expected Time Complexity: O(E*logE), where E is the number of edges in the Tree.
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{5}
There might be edges with similar values

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def maxBinTreeGCD(self, arr, N):

        # code here 

Solutions:
import math

class Solution:

	def maxBinTreeGCD(self, arr, N):
		possible_pairs = []
		arr.sort()
		ans = 0
		for i in range(len(arr) - 1):
			if arr[i][0] == arr[i + 1][0]:
				ans = max(ans, math.gcd(arr[i][1], arr[i + 1][1]))
				i += 1
			else:
				continue
		return ans


class Solution:

	def maxBinTreeGCD(self, arr, N):
		arr.sort()
		n = len(arr)
		maxx = 0
		if N <= 2:
			return 0
		for i in range(n - 1):
			if arr[i][0] == arr[i + 1][0]:
				maxx = max(maxx, gcd(arr[i][1], arr[i + 1][1]))
		return maxx


from math import gcd

class Solution:

	def maxBinTreeGCD(self, arr, N):
		arr.sort(key=lambda x: x[0])
		length = len(arr)
		maximum = -99999
		i = 0
		while i < length - 1:
			if arr[i][0] == arr[i + 1][0]:
				maximum = max(maximum, gcd(arr[i][1], arr[i + 1][1]))
				i += 2
			else:
				i += 1
		if maximum == -99999:
			return 0
		return maximum


class Solution:

	def maxBinTreeGCD(self, arr, N):
		if N <= 2:
			return 0
		arr.sort()
		a = arr[0]
		ans = 0
		for i in range(1, len(arr)):
			b = arr[i]
			if a[0] == b[0]:
				ans = max(ans, gcd(a[1], b[1]))
			a = b
		return ans


import math

class Solution:

	def maxBinTreeGCD(self, arr, N):
		maxgcd = 0
		arr.sort(reverse=True)
		while arr and len(arr) > 1:
			if arr[-1][0] == arr[-2][0]:
				(p, s1) = arr.pop()
				(p2, s2) = arr.pop()
				maxgcd = max(maxgcd, math.gcd(s1, s2))
			else:
				arr.pop()
		return maxgcd


import math

class Solution:

	def maxBinTreeGCD(self, arr, N):
		if N <= 2:
			return 0
		arr = sorted(arr, key=lambda x: x[0])
		st = [arr[0]]
		ans = 0
		k = 0
		for i in range(1, N - 1):
			if st[-1][0] == arr[i][0]:
				k = math.gcd(st[-1][1], arr[i][1])
			else:
				st.append(arr[i])
			ans = max(k, ans)
		return ans


class Solution:

	def maxBinTreeGCD(self, arr, N):

		def gcd(a, b):
			if a == 0:
				return b
			return gcd(b % a, a)
		d = {}
		for i in arr:
			a = i[0]
			b = i[1]
			if a in d:
				d[a].append(b)
			else:
				d[a] = [b]
		ans = 0
		for i in d:
			cur = d[i]
			if len(cur) == 2:
				ans = max(ans, gcd(cur[0], cur[1]))
		return ans


class Solution:

	def maxBinTreeGCD(self, arr, n):
		arr.sort()
		if n == 0 or n == 1:
			return 0
		a = arr[0]
		t = 0
		for i in range(1, n - 1):
			b = arr[i]
			if a[0] == b[0]:
				n = max(a[1], b[1])
				dv = min(a[1], b[1])
				ps = 0
				while 1:
					r = n % dv
					if r == 0:
						ps = dv
						break
					n = dv
					dv = r
				t = max(t, ps)
			a = b
		return t


class Solution:

	def maxBinTreeGCD(self, arr, N):
		if len(arr) == 0 or len(arr) == 1:
			return 0
		arr.sort()
		a = arr[0]
		m = -99999999
		for i in range(1, len(arr)):
			b = arr[i]
			if a[0] == b[0]:
				mi = min(a[1], b[1])
				while mi > 0:
					if a[1] % mi == 0 and b[1] % mi == 0:
						break
					else:
						mi -= 1
				m = max(m, mi)
			a = b
		if m <= 0:
			return 0
		return m


from collections import defaultdict
from math import gcd

class Solution:

	def maxBinTreeGCD(self, arr, N):
		adj = defaultdict(lambda : [])
		for (i, j) in arr:
			adj[i].append(j)
		maxi = 0
		for item in adj.values():
			if len(item) == 2:
				maxi = max(maxi, gcd(item[0], item[1]))
		return maxi


import math

class Solution:

	def maxBinTreeGCD(self, arr, N):
		arr.sort(key=lambda x: x[0])
		a = {}
		max = 0
		for i in range(N - 1):
			if arr[i][0] in a:
				m = gcd(a[arr[i][0]], arr[i][1])
				if m > max:
					max = m
			else:
				a[arr[i][0]] = arr[i][1]
		return max


import math

class Solution:

	def maxBinTreeGCD(self, arr, N):
		a = {}
		max = 0
		for i in range(N - 1):
			if arr[i][0] in a:
				m = gcd(a[arr[i][0]], arr[i][1])
				if m > max:
					max = m
			else:
				a[arr[i][0]] = arr[i][1]
		return max


class Solution:

	def maxBinTreeGCD(self, arr, N):
		arr.sort()
		ans = 0
		a = 0
		b = 0
		gc = 0
		node = -1
		cnt = 0

		def gcd(a, b):
			if b == 0:
				return a
			return gcd(b, a % b)
		for el in arr:
			if node != el[0]:
				node = el[0]
				a = el[1]
				cnt = 0
			else:
				b = el[1]
				if cnt == 0:
					gc = gcd(max(a, b), min(a, b))
					cnt += 1
				else:
					gc = gcd(max(gc, b), min(gc, b))
				ans = max(ans, gc)
		return ans


import math

class Solution:

	def maxBinTreeGCD(self, arr, N):
		arr.sort()
		total = 0
		if N <= 2:
			return 0
		for i in range(N - 2):
			if arr[i][0] == arr[i + 1][0]:
				result = math.gcd(arr[i][1], arr[i + 1][1])
				if total < result:
					total = result
		return total


class Solution:

	def maxBinTreeGCD(self, arr, N):
		if len(arr) == 1:
			return 0
		arr.sort(key=lambda x: x[0], reverse=True)
		res = 0
		i = 0
		while i < len(arr) - 1:
			if arr[i][0] == arr[i + 1][0]:
				gcd = self.gcd(arr[i][1], arr[i + 1][1])
				if gcd > res:
					res = gcd
				i = i + 2
			else:
				i = i + 1
		return res

	def gcd(self, a, b):
		if a == b:
			return a
		if a > b:
			return gcd(a - b, b)
		else:
			return gcd(a, b - a)


import math

class Solution:

	def maxBinTreeGCD(self, arr, N):
		dict1 = {}
		for ele in arr:
			if not dict1.get(ele[0], 0):
				dict1[ele[0]] = [ele[1]]
			else:
				dict1[ele[0]] += [ele[1]]
		maxi = -9
		for (key, value) in dict1.items():
			if len(value) == 2:
				ans = math.gcd(value[0], value[1])
				if ans > maxi:
					maxi = ans
		if maxi == -9:
			return 0
		return maxi


class Solution:

	def maxBinTreeGCD(self, arr, N):
		arr.sort()
		mx = 0
		if N <= 2:
			return 0
		for i in range(N - 2):
			if arr[i][0] == arr[i + 1][0]:
				mx = max(mx, self.gcd(arr[i][1], arr[i + 1][1]))
		return mx

	def gcd(self, a, b):
		if b == 0:
			return a
		else:
			return self.gcd(b, a % b)


def getGcd(a, b):
	if a == 0:
		return b
	if b == 0:
		return a
	return getGcd(b % a, a)

class Solution:

	def maxBinTreeGCD(self, arr, N):
		gcd = 0
		arr.sort(key=lambda x: x[0])
		for i in range(1, N - 1):
			if arr[i][0] == arr[i - 1][0]:
				g = getGcd(min(arr[i][1], arr[i - 1][1]), max(arr[i][1], arr[i - 1][1]))
				if g > gcd:
					gcd = g
		return gcd


import math

class Solution:

	def maxBinTreeGCD(self, arr, N):
		(hmap, res) = ({}, 0)
		for a in arr:
			if hmap.get(a[0]):
				res = max(res, math.gcd(hmap.get(a[0])[0], a[1]))
			else:
				hmap[a[0]] = [a[1]]
		return res


class Solution:

	def maxBinTreeGCD(self, arr, N):
		map = {}
		for i in arr:
			if i[0] not in map:
				map[i[0]] = [i[1]]
			else:
				map[i[0]].append(i[1])
		res = []
		for i in map:
			if len(map[i]) > 1:
				res.append(gcd(map[i][0], map[i][1]))
		return max(res) if len(res) else 0


class Solution:

	def maxBinTreeGCD(self, arr, N):
		if N == 1 or N == 2:
			return 0
		arr.sort()
		ans = 0
		res = []
		for i in range(len(arr) - 1):
			if arr[i][0] == arr[i + 1][0]:
				mini = min(arr[i][1], arr[i + 1][1])
				maxi = 0
				for j in range(1, mini + 1):
					if arr[i][1] % j == 0 and arr[i + 1][1] % j == 0:
						maxi = max(maxi, j)
				ans = max(maxi, ans)
		return ans


from math import gcd

class Solution:

	def maxBinTreeGCD(self, a, n):
		ans = 0
		gd = 0
		a.sort()
		n = len(a)
		k = 0
		for i in range(n - 1):
			gd = gcd(gd, a[i][1])
			if a[i][0] == a[i + 1][0]:
				k = 1
			else:
				if k == 1:
					ans = max(ans, gd)
				gd = 0
				k = 0
		if k == 1:
			ans = max(ans, gd)
		return ans


import math

class Solution:

	def maxBinTreeGCD(self, arr, N):
		if N == 1 or N == 2:
			return 0
		ans = 0
		arr.sort()
		for i in range(len(arr) - 1):
			if arr[i][0] == arr[i + 1][0]:
				ans = max(ans, math.gcd(arr[i][1], arr[i + 1][1]))
		return ans


import math

class Solution:

	def maxBinTreeGCD(self, arr, N):
		mx = 0
		arr.sort()
		for i in range(N - 2):
			if arr[i][0] == arr[i + 1][0]:
				a = math.gcd(arr[i][1], arr[i + 1][1])
				if a > mx:
					mx = a
		return mx


import math

class Solution:

	def maxBinTreeGCD(self, arr, N):
		if len(arr) == 0:
			return 0
		m = 0
		arr = sorted(arr)
		for i in range(len(arr) - 1):
			(a, b) = (arr[i], arr[i + 1])
			if a[0] == b[0]:
				if m < math.gcd(a[1], b[1]):
					m = math.gcd(a[1], b[1])
		return m


from fractions import gcd

class Solution:

	def maxBinTreeGCD(self, arr, N):
		d = {}
		for i in arr:
			if i[0] not in d:
				d[i[0]] = [i[1]]
			else:
				d[i[0]].append(i[1])
		ans = []
		for (i, j) in d.items():
			if len(j) == 2:
				ans.append(gcd(j[0], j[1]))
		try:
			return max(ans)
		except:
			return 0


from math import gcd

class Solution:

	def maxBinTreeGCD(self, arr, N):
		if len(arr) == 1 or len(arr) == 0:
			return 0
		arr.sort()
		a = arr[0]
		res = 0
		for i in range(1, len(arr)):
			b = arr[i]
			if b[0] == a[0]:
				res = max(res, gcd(a[1], b[1]))
			a = b
		return res


import math

class Solution:

	def maxBinTreeGCD(self, arr, N):
		gcdenom = 0
		arr.sort()
		for i in range(len(arr) - 1):
			if arr[i][0] == arr[i + 1][0]:
				gcdenom = max(gcdenom, math.gcd(arr[i][1], arr[i + 1][1]))
		return gcdenom


import math

class Solution:

	def maxBinTreeGCD(self, arr, N):
		pairs = {}
		for num in arr:
			(a, b) = (num[0], num[1])
			if a not in pairs:
				pairs[a] = [b]
			else:
				pairs[a].append(b)
		maxi = -10 ** 5
		for pair in pairs:
			if len(pairs[pair]) > 1:
				maxi = max(math.gcd(pairs[pair][0], pairs[pair][1]), maxi)
		if maxi == -10 ** 5:
			return 0
		return maxi


from math import gcd

class Solution:

	def maxBinTreeGCD(self, arr, N):
		arr.sort()
		length = len(arr)
		maxi = float('-inf')
		i = 0
		while i < length - 1:
			if arr[i][0] == arr[i + 1][0]:
				maxi = max(maxi, gcd(arr[i][1], arr[i + 1][1]))
				i += 2
			else:
				i += 1
		if maxi == float('-inf'):
			return 0
		return maxi


from math import gcd

class Solution:

	def maxBinTreeGCD(self, arr, N):
		dict1 = dict()
		length = len(arr)
		maximum = -9999
		for i in range(length):
			if arr[i][0] not in dict1:
				dict1[arr[i][0]] = arr[i][1]
			else:
				maximum = max(maximum, gcd(dict1[arr[i][0]], arr[i][1]))
		if maximum == -9999:
			return 0
		return maximum
		for i in dict1:
			if len(dict1[i]) == 2:
				maximum = max(maximum, gcd(dict1[i][0], dict1[i][1]))
		if maximum == -9999:
			return 0
		return maximum


import math
from collections import defaultdict

class Solution:

	def maxBinTreeGCD(self, arr, N):
		mx = 0
		mp = defaultdict(list)
		for i in arr:
			mp[i[0]].append(i[1])
		for (i, v) in mp.items():
			if len(v) != 2:
				continue
			mx = max(mx, math.gcd(v[0], v[1]))
		return mx


class Solution:

	def gcd(self, a, b):
		result = min(a, b)
		while result:
			if a % result == 0 and b % result == 0:
				break
			result -= 1
		return result

	def maxBinTreeGCD(self, arr, N):
		i = 1
		mgcd = 0
		if N <= 2:
			return 0
		arr.sort()
		ht = {}
		nodes = 0
		pairs = len(arr)
		while nodes < N and i < pairs:
			if N - nodes >= 2:
				hn = [arr[i - 1][0], arr[i - 1][1], arr[i][0], arr[i][1]]
				for n in hn:
					if n not in ht:
						ht[n] = 1
						nodes += 1
					else:
						ht[n] += 1
				if arr[i - 1][0] == arr[i][0]:
					m = self.gcd(arr[i - 1][1], arr[i][1])
					mgcd = max(m, mgcd)
					i += 2
				else:
					i += 1
			else:
				nodes += 1
				i += 1
		return mgcd


class Solution:

	def maxBinTreeGCD(self, arr, N):
		if N == 0:
			return 0
		arr.sort()
		maxgcd = 0
		for i in range(len(arr) - 1):
			a = arr[i]
			b = arr[i + 1]
			while len(a) <= 1:
				a = arr[i]
				b = arr[i + 1]
				i += 1
			if len(a) != 0 and len(b) != 0 and (a[0] == b[0]):
				i += 1
				x = a[1]
				y = b[1]
				gcd = min(x, y)
				while gcd:
					if x % gcd == 0 and y % gcd == 0:
						break
					gcd -= 1
				if gcd > maxgcd:
					maxgcd = gcd
		return maxgcd


import math as m

class Solution:

	def maxBinTreeGCD(self, arr, N):
		arr.sort(key=lambda x: x[0])
		max_gcd = 0
		for (i, a) in enumerate(arr):
			if i != 0:
				if arr[i][0] == arr[i - 1][0]:
					max_gcd = max(max_gcd, m.gcd(arr[i - 1][1], arr[i][1]))
		return max_gcd


import math

class Solution:

	def maxBinTreeGCD(self, arr, N):
		d = {}
		l = []
		for i in arr:
			if i[0] not in d:
				d[i[0]] = i[1:]
			else:
				d[i[0]] += i[1:]
		for i in d:
			if len(d[i]) >= 2:
				l.append(math.gcd(d[i][0], d[i][1]))
			else:
				l.append(0)
		if l:
			return max(l)
		return 0


INT_MIN = -(1 << 63)

class Solution:

	def gcd(self, a, b):
		if b > a:
			(a, b) = (b, a)
		while b > 0:
			r = a % b
			a = b
			b = r
		return a

	def maxBinTreeGCD(self, arr, N):
		arr.sort(key=lambda item: item[0])
		max_gcd = INT_MIN
		i = 0
		j = 1
		while j < len(arr):
			if arr[i][0] == arr[j][0]:
				max_gcd = max(max_gcd, self.gcd(arr[i][1], arr[j][1]))
			i += 1
			j += 1
		return 0 if max_gcd == INT_MIN else max_gcd


class Solution:

	def maxBinTreeGCD(self, arr, N):
		arr.sort()
		m = 0
		x = 0
		for i in range(len(arr) - 1):
			if arr[i][0] == arr[i + 1][0]:
				x = gcd(arr[i][1], arr[i + 1][1])
			m = max(m, x)
		return m


class Solution:

	def gcd(self, a, b):
		if b == 0:
			return a
		return (b, a % b)

	def maxBinTreeGCD(self, arr, N):
		i = 0
		arr.sort()
		maxGCD = 0
		n = len(arr)
		while i < n - 1:
			if arr[i][0] == arr[i + 1][0]:
				maxGCD = max(maxGCD, gcd(arr[i][1], arr[i + 1][1]))
			i += 1
		return maxGCD


from collections import defaultdict

class Solution:

	def maxBinTreeGCD(self, arr, N):

		def gcd(a, b):
			if a == 0:
				return b
			return gcd(b % a, a)
		if len(arr) < 2:
			return 0
		mapp = defaultdict(list)
		res = 0
		for (i, j) in arr:
			mapp[i].append(j)
		for key in mapp:
			if len(mapp[key]) == 2:
				res = max(res, gcd(mapp[key][0], mapp[key][1]))
		return res


import math

class Solution:

	def maxBinTreeGCD(self, arr, N):
		maxgcd = 0
		arr.sort(key=lambda x: x[0])
		for i in range(1, len(arr)):
			if arr[i][0] == arr[i - 1][0]:
				g = math.gcd(arr[i][1], arr[i - 1][1])
				if g > maxgcd:
					maxgcd = g
		return maxgcd


import math

class Solution:

	def maxBinTreeGCD(self, arr, N):
		mp = {}
		for i in arr:
			if i[0] in mp:
				mp[i[0]].append(i[1])
			else:
				mp[i[0]] = [i[1]]

		def gcd(arr):
			g = arr[0]
			for i in range(1, len(arr)):
				g = math.gcd(g, arr[i])
			return g
		mx = -1
		for k in mp:
			if len(mp[k]) > 1:
				mx = max(mx, gcd(mp[k]))
		return mx if mx != -1 else 0


from math import inf

class Solution:

	def maxBinTreeGCD(self, arr, N):

		def gcd(a, b):
			if a == 0:
				return b
			if b == 0:
				a
			if a == b:
				return a
			if a > b:
				return gcd(a - b, b)
			return gcd(a, b - a)
		maxs = 0
		arr.sort()
		if N <= 2:
			return 0
		for i in range(N - 2):
			if arr[i][0] == arr[i + 1][0]:
				maxs = max(maxs, gcd(arr[i][1], arr[i + 1][1]))
		return maxs


import math

class Solution:

	def maxBinTreeGCD(self, arr, N):
		if N == 0 or N == 1 or N == 2:
			return 0
		maxgcd = 0
		pairsdict = {}
		for i in arr:
			pairsdict[i[0]] = pairsdict.get(i[0], [])
			pairsdict[i[0]].append(i[1])
		for (key, value) in pairsdict.items():
			if len(value) == 2:
				gcd = math.gcd(value[0], value[1])
				if gcd > maxgcd:
					maxgcd = gcd
		return maxgcd


import math

class Solution:

	def maxBinTreeGCD(self, arr, N):
		maxGcd = 0
		parent_son_dict = {}
		for pair in arr:
			parent_son_dict[pair[0]] = parent_son_dict.get(pair[0], [])
			parent_son_dict[pair[0]].append(pair[1])
		for (key, value) in parent_son_dict.items():
			if len(value) == 2:
				gcd = math.gcd(value[0], value[1])
				if gcd > maxGcd:
					maxGcd = gcd
		return maxGcd


class Solution:

	def maxBinTreeGCD(self, arr, N):
		dic = {}
		mx = 0
		for i in arr:
			try:
				dic[i[0]] += [i[1]]
			except:
				dic[i[0]] = [i[1]]
		for i in dic:
			if len(dic[i]) > 1:
				(a, b) = (min(dic[i]), max(dic[i]))
				mx = max(mx, self.gcd(a, b))
		return mx

	def gcd(self, a, b):
		if b == 0:
			return a
		return self.gcd(b, a % b)


def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

class Solution:

	def maxBinTreeGCD(self, arr, N):
		d = {}
		for e in arr:
			if e[0] in d:
				d[e[0]].append(e[1])
			else:
				d[e[0]] = [e[1]]
		mx = 0
		for e in d:
			if len(d[e]) == 2:
				mx = max(gcd(min(d[e]), max(d[e])), mx)
		return mx


class Solution:

	def maxBinTreeGCD(self, arr, N):
		h = {}
		for (p, c) in arr:
			h[p] = h.get(p, []) + [c]
		mx = 0

		def func(arr):
			if len(arr) == 0 or len(arr) == 1:
				return 0
			val = min(arr[0], arr[1])
			while val:
				if arr[0] % val == 0 and arr[1] % val == 0:
					return val
				val -= 1
			return val
		for i in h:
			mx = max(mx, func(h[i]))
		return mx


class Solution:

	def gcd_hcf(self, a, b):
		if b == 0:
			return a
		return self.gcd_hcf(b, a % b)

	def maxBinTreeGCD(self, arr, N):
		if len(arr) == 0 or len(arr) == 1:
			return 0
		arr.sort()
		ans = 0
		a = arr[0]
		for i in range(1, len(arr)):
			b = arr[i]
			if a[0] == b[0]:
				ans = max(ans, self.gcd_hcf(a[1], b[1]))
			a = b
		return ans


class Solution:

	def gcd_hcf(a, b):
		if b == 0:
			return a
		return gcd_hcf(b, a % b)

	def maxBinTreeGCD(self, arr, N):
		d = {}
		for pair in arr:
			(u, v) = (pair[0], pair[1])
			if u not in d:
				d[u] = []
			d[u].append(v)
		ans = 0
		for i in d:
			if len(d[i]) == 1:
				pass
			else:
				(a, b) = (d[i][0], d[i][1])
				ans = max(ans, gcd(a, b))
		return ans


def computeGCD(x, y):
	if x > y:
		small = y
	else:
		small = x
	for i in range(1, small + 1):
		if x % i == 0 and y % i == 0:
			gcd = i
	return gcd

class Solution:

	def maxBinTreeGCD(self, arr, N):
		if N == 1 or len(arr) == 1:
			return 0
		d = {}
		for items in arr:
			if items[0] in d:
				d[items[0]].append(items[1])
			else:
				d[items[0]] = []
				d[items[0]].append(items[1])
		l = []
		for items in d:
			if len(d[items]) > 1:
				l.append(gcd(d[items][0], d[items][1]))
		if len(l) != 0:
			return max(l)
		else:
			return 0
		return max(l)


class Solution:

	def maxBinTreeGCD(self, arr, N):

		def gcd(a, b):
			return a if b == 0 else gcd(b, a % b)
		result = 0
		val = {}
		for value in arr:
			if value[0] not in val:
				val[value[0]] = value[1]
			else:
				val[value[0]] = gcd(val[value[0]], value[1])
				result = max(val[value[0]], result)
		return result


import math

class Solution:

	def maxBinTreeGCD(self, arr, N):
		arr.sort()
		ans = 0
		value = {}
		for val in arr:
			if val[0] not in value:
				value[val[0]] = val[1]
			else:
				value[val[0]] = math.gcd(value[val[0]], val[1])
				ans = max(ans, value[val[0]])
		return ans


from collections import defaultdict

class Solution:

	def gcd(self, a, b):
		if a % b == 0:
			return b
		else:
			(a, b) = (b, a % b)
		return self.gcd(a, b)

	def maxBinTreeGCD(self, arr, N):
		childs = defaultdict(list)
		for element in arr:
			a = element[0]
			b = element[1]
			childs[a].append(b)
		max_gcd = 0
		for key in childs:
			values = childs[key]
			if len(values) == 2:
				a = values[0]
				b = values[1]
				max_gcd = max(self.gcd(a, b), max_gcd)
		return max_gcd


class Solution:

	def maxBinTreeGCD(self, arr, N):
		hmap = {}
		for e in arr:
			par = e[0]
			ch = e[1]
			if par in hmap:
				hmap[par].append(ch)
			else:
				hmap[par] = [ch]
		ans = 0
		for k in hmap:
			if len(hmap[k]) == 2:
				ans = max(ans, self.gcd(hmap[k][0], hmap[k][1]))
		return ans

	def gcd(self, a, b):
		if a == 0:
			return b
		return self.gcd(b % a, a)


from math import gcd

def func(arr):
	n = len(arr)
	arr.sort()
	if n == 1 or n == 0:
		return 0
	ans = -10000000000
	for i in range(n - 1):
		if arr[i][0] == arr[i + 1][0]:
			ans = max(ans, gcd(arr[i][1], arr[i + 1][1]))
	if ans == -10000000000:
		ans = 0
	return ans

class Solution:

	def maxBinTreeGCD(self, arr, N):
		return func(arr)


class Solution:

	def maxBinTreeGCD(self, arr, N):

		def gcd(a, b):
			(l, s) = (max(a, b), min(a, b))
			if l % s == 0:
				return s
			return gcd(l % s, s)
		table = {}
		for i in arr:
			table[i[0]] = table.get(i[0], [])
			table[i[0]].append(i[1])
		maxgcd = 0
		for i in table:
			if len(table[i]) == 2:
				maxgcd = max(maxgcd, gcd(*table[i]))
		return maxgcd


class Solution:

	def gcd(a, b):
		if b == 0:
			return abs(a)
		return gcd(b, a % b)

	def maxBinTreeGCD(self, arr, N):
		tdict = {}
		for pair in arr:
			if pair[0] in tdict:
				tdict[pair[0]].append(pair[1])
			else:
				tdict[pair[0]] = [pair[1]]
		maxi = 0
		for parent in tdict:
			if len(tdict[parent]) == 2:
				maxi = max(maxi, gcd(tdict[parent][0], tdict[parent][1]))
		return maxi


class Solution:
	m = 0

	def gcd(self, a, b):
		if b == 0:
			return a
		return self.gcd(b, a % b)

	def f(self, a, b):
		if a < Solution.m or b < Solution.m:
			return
		x = self.gcd(a, b)
		if x > Solution.m:
			Solution.m = x
		return

	def maxBinTreeGCD(self, a, N):
		Solution.m = 0
		a.sort(reverse=True)
		i = 0
		while i + 1 < N - 1:
			if a[i][0] == a[i + 1][0]:
				self.f(a[i][1], a[i + 1][1])
				i += 2
			else:
				i += 1
		return Solution.m


class Solution:

	def maxBinTreeGCD(self, arr, N):
		if len(arr) == 0 or len(arr) == 1:
			return 0
		arr.sort()
		a = arr[0]
		max_ = 0
		for i in range(1, len(arr)):
			b = arr[i]
			if a[0] == b[0]:
				max_ = max(max_, gcd(a[1], b[1]))
			a = b
		return max_


import math as m

class Solution:

	def maxBinTreeGCD(self, arr, N):
		d = dict()
		for i in arr:
			if i[0] in d:
				d[i[0]].append(i[1])
			else:
				d[i[0]] = [i[1]]
		res = []
		for i in d:
			if len(d[i]) == 1:
				res.append(0)
			else:
				res.append(m.gcd(d[i][0], d[i][1]))
		if len(res) == 0:
			return 0
		return max(res)


class Solution:

	def gcd(self, l):
		if l[0] == l[1]:
			return l[0]
		if l[0] < l[1]:
			return self.gcd([l[0], l[1] - l[0]])
		else:
			return self.gcd([l[1], l[0] - l[1]])

	def maxBinTreeGCD(self, arr, N):
		d = {}
		for e in arr:
			if e[0] not in d:
				d[e[0]] = [e[1]]
			else:
				d[e[0]].append(e[1])
		res = 0
		for k in d:
			if len(d[k]) == 2:
				t = self.gcd(d[k])
				res = max(res, t)
		return res


from math import gcd

class Solution:

	def maxBinTreeGCD(self, arr, N):
		d1 = {}
		for l1 in arr:
			if d1.get(l1[0], 0) == 0:
				d1[l1[0]] = [l1[1]]
			else:
				d1[l1[0]] += [l1[1]]
		max_gcd = 0
		siblings_exist_flag = False
		for key in d1:
			if len(d1[key]) == 2:
				siblings_exist_flag = True
				curr_gcd = gcd(d1[key][0], d1[key][1])
				if curr_gcd > max_gcd:
					max_gcd = curr_gcd
		if siblings_exist_flag == False:
			max_gcd = 0
		return max_gcd


class Solution:

	def gcd(self, a, b):
		if a == b:
			return a
		if a > b:
			return self.gcd(a - b, b)
		return self.gcd(a, b - a)

	def maxBinTreeGCD(self, arr, N):
		dct = dict()
		for val in arr:
			if val[0] not in dct:
				dct[val[0]] = [val[1]]
			else:
				dct[val[0]].append(val[1])
		maximum = 0
		for val in dct.values():
			if len(val) < 2:
				continue
			maximum = max(maximum, self.gcd(val[0], val[1]))
		return maximum


from math import gcd

class Solution:

	def maxBinTreeGCD(self, arr, N):
		max_gcd = 0
		arr.sort()
		first = True
		for i in arr:
			if first == True:
				a = i
				first = False
			elif i[0] == a[0]:
				b = i
				max_gcd = max(max_gcd, gcd(a[1], b[1]))
				first = True
			else:
				a = i
				first = False
		return max_gcd