Chef stumbled upon B black nodes and W white nodes and now wants to construct a tree using them.

Chef is bamboozled by the total number of trees that can be constructed using these nodes. To reduce this count, Chef considered only those trees which have at least one diameter that has alternating colors i.e. a black node is followed by a white node and a white node is followed by a black node.

Help Chef in finding out the tree with the minimum possible diameter among all the trees that satisfies the above condition. If no tree satisfies the above conditions, print -1. If multiple trees satisfies the above condition, print any.

------ Input Format ------ 

- The first line contains a single integer T - the number of test cases. Then the test cases follow.
- The first and only line of each test case contains two space separated integers B, W representing the number of black and white nodes respectively.

------ Output Format ------ 

- If a tree can be constructed that fulfils all the requirements then
- In the first line, output a string of length B + W in which the i^{th} character (1-based indexing) is either W or B denoting the colour of the i^{th} node as black or white respectively.
- In the following B + W - 1 lines, output two integers U and V denoting an edge between U^{th} and V^{th} node.
- If no tree fulfils the requirements print -1 in a single line. 

------ Constraints ------ 

$1 ≤ T ≤ 100$
$0 ≤ B, W ≤ 1000$
$1 ≤ B + W ≤ 1000$

----- Sample Input 1 ------ 
3
1 1
0 2
1 2

----- Sample Output 1 ------ 
WB
2 1
-1
WBW
1 2
2 3

----- explanation 1 ------ 
Test case $1$: The tree has only one path between the nodes $1$ and $2$ which is the diameter and also alternating in color. The checker will handle multiple possible answers so you can also swap the colors of the node to achieve the same result. 

Test case $2$: There is only one tree possible and its diameter would consist of all white nodes only. Therefore there is no tree which satisfies the given conditions.

Difficulty: VERY_HARD
Tags: Tree algorithms

Graph algorithms

Data structures
Skill types: Data structures

Starter code:

Solutions:
def solve(W, B):
	N = W + B
	if N == 1:
		if W:
			print('W')
		else:
			print('B')
		return
	elif N == 2:
		if W == 0 or B == 0:
			print(-1)
			return
		print('WB')
		print(1, 2)
	else:
		if W == 0 or B == 0:
			print(-1)
			return
		if B > 1:
			st = 'BWB'
			B -= 2
			W -= 1
		else:
			st = 'WBW'
			W -= 2
			B -= 1
		st = st + 'B' * B + 'W' * W
		print(st)
		print(1, 2)
		print(2, 3)
		for end in range(4, 4 + B):
			print(2, end)
		for end in range(4 + B, 4 + W + B):
			print(2, end)
for case in range(int(input())):
	(B, W) = map(int, input().split())
	solve(W, B)


for _ in range(int(input())):
	(b, w) = map(int, input().split())
	o_b = int(b)
	o_w = int(w)
	if b == 1 and w == 1:
		print('WB')
		print(1, 2)
		continue
	if w == 0 and b == 1:
		print('B')
		continue
	elif w == 1 and b == 0:
		print('W')
		continue
	elif w == 0:
		print(-1)
		continue
	elif b == 0:
		print(-1)
		continue
	if w > b:
		new_string = 'WBW'
		w -= 2
		b -= 1
		print(new_string + w * 'W' + b * 'B')
		print(1, 2)
		print(2, 3)
		if len(new_string) < o_b + o_w:
			for i in range(len(new_string) + 1, o_w + o_b + 1):
				print(2, i)
	else:
		new_string = 'BWB'
		b -= 2
		w -= 1
		print(new_string + b * 'B' + w * 'W')
		print(1, 2)
		print(2, 3)
		if len(new_string) < o_b + o_w:
			for i in range(len(new_string) + 1, o_w + o_b + 1):
				print(2, i)


t = int(input())
for i in range(t):
	[b, w] = list(map(int, input().split()))
	if b == 0 and w == 1:
		print('W')
		continue
	elif b == 1 and w == 0:
		print('B')
		continue
	elif b == 0 or w == 0:
		print(-1)
		continue
	if b > w:
		print('BW' + 'B' * (b - 1) + 'W' * (w - 1))
	if w >= b:
		print('WB' + 'W' * (w - 1) + 'B' * (b - 1))
	for j in range(b + w):
		if j == 1:
			continue
		print(2, j + 1)