Read problems statements in Mandarin Chinese and Russian as well. 

	The following graph G is called a Petersen graph and its vertices have been numbered from 0 to 9. Some letters have also been assigned to vertices of G, as can be seen from the following picture:

	Let's consider a walk W in graph G, which consists of L vertices W_{1}, W_{2}, ..., W_{L}, such that W_{i} is connected with W_{i + 1} for 1 ≤ i < L. A string S of L letters 'A'-'E' is realized by walk W if the sequence of letters written along W is equal to S. Vertices can be visited multiple times while walking along W.

For example, S = 'ABBECCD' is realized by W = (0, 1, 6, 9, 7, 2, 3).
Your task is to determine whether there is a walk W which realizes a given string S in graph G, and if so, find the lexicographically least such walk.

------ Input ------ 

	The first line of the input contains one integer T denoting the number of testcases to process.

	The only line of each testcase contains one string S. It is guaranteed that S only consists of symbols 'A'-'E'.

------ Output ------ 

	The output should contain exactly T lines, one line per each testcase in the order of their appearance. For each testcase, if there is no walk W which realizes S, then output -1. Otherwise, you should output the least lexicographical walk W which realizes S. Since all of the vertices are numbered from 0 to 9, then it can be encoded as a string consisting of symbols '0'-'9' (see the "Examples" section for more details).

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

1 ≤ T ≤ 8;
1 ≤ |S| ≤ 100000(10^{5}).

----- Sample Input 1 ------ 
2
AAB
AABE
----- Sample Output 1 ------ 
501
-1

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Graph traversal


Solutions:
from sys import stdin
input = stdin.readline
P_nbr = ((1, 4, 5), (0, 2, 6), (1, 3, 7), (2, 4, 8), (0, 3, 9), (0, 7, 8), (1, 8, 9), (2, 5, 9), (3, 5, 6), (4, 6, 7), (0, 1, 2, 3, 4), (5, 6, 7, 8, 9))
P_val = list('ABCDEABCDE')
P_sym = list('0123456789')
T = int(input())
for tx in range(T):
	S = input().strip()
	opts = [[[], 10], [[], 11]]
	for c in S:
		deadend = 0
		for opt in opts:
			for adj in P_nbr[opt[1]]:
				if P_val[adj] == c:
					opt[0].append(P_sym[adj])
					opt[1] = adj
					break
			else:
				opt.clear()
				deadend += 1
		if deadend:
			if len(opts) == deadend:
				print('-1')
				break
			for _ in range(deadend):
				opts.remove([])
	else:
		print(''.join(min(opts)[0]))


a = ['a', 'b', 'c', 'd', 'e', 'A', 'B', 'C', 'D', 'E']
b = ['5', '6', '7', '8', '9', '0', '1', '2', '3', '4']
c = [('A', 'c', 'd'), ('B', 'd', 'e'), ('C', 'a', 'e'), ('D', 'a', 'b'), ('E', 'b', 'c'), ('a', 'E', 'B'), ('b', 'A', 'C'), ('c', 'B', 'D'), ('d', 'E', 'C'), ('e', 'A', 'D')]
T = int(input())
for t in range(T):
	In = input()
	S = list(In)
	result = ''
	if len(set(S)) == 1:
		temp = S[0]
		for i in range(len(S)):
			result += b[a.index(temp)]
			temp = temp.swapcase()
	else:
		S[0] = S[0].swapcase()
		result += b[a.index(S[0])]
		for i in range(1, len(S)):
			if S[i] in c[a.index(S[i - 1])]:
				result += b[a.index(S[i])]
			elif S[i].swapcase() in c[a.index(S[i - 1])]:
				S[i] = S[i].swapcase()
				result += b[a.index(S[i])]
			else:
				result = '-1'
				break
		if result == '-1':
			result = ''
			S = list(In)
			result += b[a.index(S[0])]
			for i in range(1, len(S)):
				if S[i] in c[a.index(S[i - 1])]:
					result += b[a.index(S[i])]
				elif S[i].swapcase() in c[a.index(S[i - 1])]:
					S[i] = S[i].swapcase()
					result += b[a.index(S[i])]
				else:
					result = '-1'
					break
	print(result)


from sys import stdin
input = stdin.readline
P_nbr = ((1, 4, 5), (0, 2, 6), (1, 3, 7), (2, 4, 8), (0, 3, 9), (0, 7, 8), (1, 8, 9), (2, 5, 9), (3, 5, 6), (4, 6, 7), (0, 1, 2, 3, 4, 5, 6, 7, 8, 9))
P_val = list('ABCDEABCDE')
P_sym = list('0123456789')
T = int(input())
for tx in range(T):
	S = input().strip()
	opts = [('', 10)]
	for c in S:
		new_opts = []
		for (code, pos) in opts:
			for adj in P_nbr[pos]:
				if P_val[adj] == c:
					new_opts.append((code + P_sym[adj], adj))
		opts = new_opts
		if opts == []:
			print('-1')
			break
	else:
		print(min(opts)[0])


import sys
thenumberofcasestobechecked = int(sys.stdin.readline())
while thenumberofcasestobechecked > 0:
	thenumberofcasestobechecked -= 1
	thesequenceoflettersentered = list(sys.stdin.readline().rstrip('\n'))
	allthepossibleconnectiooons = [[1, 4, 5], [0, 2, 6], [1, 3, 7], [2, 4, 8], [0, 3, 9], [0, 8, 7], [1, 8, 9], [2, 5, 9], [3, 5, 6], [4, 6, 7]]
	allthepossibleconnectiooons_LETTERS = [['B', 'E', 'A'], ['A', 'C', 'B'], ['B', 'D', 'C'], ['C', 'E', 'D'], ['A', 'D', 'E'], ['A', 'D', 'C'], ['B', 'D', 'E'], ['C', 'A', 'E'], ['D', 'A', 'B'], ['E', 'B', 'C']]
	if thesequenceoflettersentered[0] == 'A':
		(startingpoint1, startingpoint2) = (0, 5)
	elif thesequenceoflettersentered[0] == 'B':
		(startingpoint1, startingpoint2) = (1, 6)
	elif thesequenceoflettersentered[0] == 'C':
		(startingpoint1, startingpoint2) = (2, 7)
	elif thesequenceoflettersentered[0] == 'D':
		(startingpoint1, startingpoint2) = (3, 8)
	else:
		(startingpoint1, startingpoint2) = (4, 9)
	copystring = thesequenceoflettersentered[1:]
	currentposition = startingpoint1
	solution1 = str(startingpoint1)
	flag1 = 0
	for letter in copystring:
		if letter in allthepossibleconnectiooons_LETTERS[currentposition]:
			currentposition = allthepossibleconnectiooons[currentposition][allthepossibleconnectiooons_LETTERS[currentposition].index(letter)]
			solution1 = solution1 + str(currentposition)
		else:
			flag1 = -1
			break
	copystring = thesequenceoflettersentered[1:]
	currentposition = startingpoint2
	solution2 = str(startingpoint2)
	flag2 = 0
	for letter in copystring:
		if letter in allthepossibleconnectiooons_LETTERS[currentposition]:
			currentposition = allthepossibleconnectiooons[currentposition][allthepossibleconnectiooons_LETTERS[currentposition].index(letter)]
			solution2 = solution2 + str(currentposition)
		else:
			flag2 = -1
			break
	if flag1 == -1 and flag2 == -1:
		print('-1')
	elif flag1 == -1:
		print(solution2)
	elif flag2 == -1:
		print(solution1)
	elif solution1 < solution2:
		print(solution1)
	else:
		print(solution2)


from collections import defaultdict
d = {'A': [0, 5], 'B': [1, 6], 'C': [2, 7], 'D': [3, 8], 'E': [4, 9]}

class Graph:

	def __init__(self, v):
		self.v = v
		self.graph = defaultdict(list)

	def addEdge(self, u, v):
		self.graph[u].append(v)
		self.graph[v].append(u)

	def route1(self, st):
		arr = []
		if len(st) == 0:
			return '-1'
		arr.append(d[st[0]][0])
		for i in range(1, len(st)):
			if d[st[i]][0] in self.graph[arr[len(arr) - 1]]:
				arr.append(d[st[i]][0])
			elif d[st[i]][1] in self.graph[arr[len(arr) - 1]]:
				arr.append(d[st[i]][1])
			else:
				return '-1'
		arr = [str(i) for i in arr]
		return ''.join(arr)

	def route2(self, st):
		arr = []
		if len(st) == 0:
			return '-1'
		arr.append(d[st[0]][1])
		for i in range(1, len(st)):
			if d[st[i]][0] in self.graph[arr[len(arr) - 1]]:
				arr.append(d[st[i]][0])
			elif d[st[i]][1] in self.graph[arr[len(arr) - 1]]:
				arr.append(d[st[i]][1])
			else:
				return '-1'
		arr = [str(i) for i in arr]
		return ''.join(arr)
g = Graph(10)
g.addEdge(0, 4)
g.addEdge(0, 5)
g.addEdge(0, 1)
g.addEdge(1, 6)
g.addEdge(1, 2)
g.addEdge(2, 3)
g.addEdge(2, 7)
g.addEdge(3, 4)
g.addEdge(3, 8)
g.addEdge(4, 9)
g.addEdge(5, 7)
g.addEdge(5, 8)
g.addEdge(6, 8)
g.addEdge(6, 9)
g.addEdge(7, 9)
n = int(input())
for i in range(n):
	st = input()
	if g.route1(st) != '-1':
		print(g.route1(st))
	elif g.route2(st) != '-1':
		print(g.route2(st))
	else:
		print('-1')


let_node = {'A': [0, 5], 'B': [1, 6], 'C': [2, 7], 'D': [3, 8], 'E': [4, 9]}
connections = {0: [1, 4, 5], 1: [0, 2, 6], 2: [1, 3, 7], 3: [2, 4, 8], 4: [0, 3, 9], 5: [0, 7, 8], 6: [1, 8, 9], 7: [2, 5, 9], 8: [3, 5, 6], 9: [4, 6, 7]}

def check_path(S, pos):
	path = str(pos)
	for val in S:
		if let_node[val][0] in connections[pos]:
			pos = let_node[val][0]
			path += str(pos)
		elif let_node[val][1] in connections[pos]:
			pos = let_node[val][1]
			path += str(pos)
		else:
			return -1
	return path
for _ in range(int(input())):
	S = list(input())
	a = check_path(S[1:], let_node[S[0]][0])
	if int(a) > 0:
		print(a)
	else:
		a = check_path(S[1:], let_node[S[0]][1])
		if int(a) > 0:
			print(a)
		else:
			print(-1)


d = dict()
d['AB'] = [0, 1]
d['AC'] = [5, 7]
d['AD'] = [5, 8]
d['AE'] = [0, 4]
d['BC'] = [1, 2]
d['BD'] = [6, 8]
d['BE'] = [6, 9]
d['CD'] = [2, 3]
d['CE'] = [7, 9]
d['DE'] = [3, 4]

def getmin(x):
	if x == 'A':
		return 0
	elif x == 'B':
		return 1
	elif x == 'C':
		return 2
	elif x == 'D':
		return 3
	elif x == 'E':
		return 4

def getans(x, y):
	if x < y:
		s = x
		s += y
		return d[s]
	else:
		s = y
		s += x
		g = d[s]
		return [g[-1], g[0]]

def getans2(val, x):
	if val == 0:
		if x == 'C' or x == 'D':
			return -1
		elif x == 'B':
			return 1
		elif x == 'E':
			return 4
		elif x == 'A':
			return 5
	if val == 1:
		if x == 'E' or x == 'D':
			return -1
		elif x == 'A':
			return 0
		elif x == 'C':
			return 2
		elif x == 'B':
			return 6
	if val == 2:
		if x == 'E' or x == 'A':
			return -1
		elif x == 'B':
			return 1
		elif x == 'D':
			return 3
		elif x == 'C':
			return 7
	if val == 3:
		if x == 'A' or x == 'B':
			return -1
		elif x == 'C':
			return 2
		elif x == 'E':
			return 4
		elif x == 'D':
			return 8
	if val == 4:
		if x == 'C' or x == 'B':
			return -1
		elif x == 'A':
			return 0
		elif x == 'D':
			return 3
		elif x == 'E':
			return 9
	if val == 5:
		if x == 'B' or x == 'E':
			return -1
		elif x == 'C':
			return 7
		elif x == 'D':
			return 8
		elif x == 'A':
			return 0
	if val == 6:
		if x == 'C' or x == 'A':
			return -1
		elif x == 'D':
			return 8
		elif x == 'E':
			return 9
		elif x == 'B':
			return 1
	if val == 7:
		if x == 'B' or x == 'D':
			return -1
		elif x == 'A':
			return 5
		elif x == 'E':
			return 9
		elif x == 'C':
			return 2
	if val == 8:
		if x == 'C' or x == 'E':
			return -1
		elif x == 'A':
			return 5
		elif x == 'B':
			return 6
		elif x == 'D':
			return 3
	if val == 9:
		if x == 'A' or x == 'D':
			return -1
		elif x == 'B':
			return 6
		elif x == 'C':
			return 7
		elif x == 'E':
			return 4
	return []
for t in range(int(input())):
	s = input()
	s = s.strip()
	l = len(s)
	ans = []
	if l == 1:
		print(getmin(s[0]))
		continue
	for i in range(l):
		ans.append(-1)
	flag = 0
	i = 1
	while i < l:
		if s[i] != s[i - 1]:
			if ans[i - 1] == -1:
				temp = getans(s[i], s[i - 1])
				ans[i] = temp[0]
				ans[i - 1] = temp[1]
			else:
				temp = getans2(ans[i - 1], s[i])
				if temp == -1:
					flag = 1
					break
				ans[i] = temp
		elif s[i] == s[i - 1] and ans[i - 1] != -1:
			temp = getans2(ans[i - 1], s[i])
			if temp == -1:
				flag = 1
				break
			ans[i] = temp
		i += 1
	if flag == 1:
		print(-1)
		continue
	i = l - 2
	while i >= 0:
		if ans[i] == -1 and ans[i + 1] == -1:
			temp = getmin(s[i])
			ans[i] = temp
			ans[i + 1] = temp + 5
		elif ans[i] == -1:
			temp = getans2(ans[i + 1], s[i])
			if temp == -1:
				flag = 1
				break
			ans[i] = temp
		elif ans[i + 1] == -1:
			temp = getans2(ans[i], s[i + 1])
			if temp == -1:
				flag = 1
				break
			ans[i + 1] = temp
		i -= 1
	if flag == 1:
		print(-1)
		continue
	if -1 in ans:
		print(-1)
		continue
	for i in ans:
		print(i, end='')
	print()