Chef likes to travel very much. He plans some travel routes and wants to know their lengths. He hired you to make these calculations. But be careful, some of the routes are incorrect. There may be some misspelling in city names or there will be no road between some two consecutive cities in the route. Also note that Chef hates to visit the same city twice during his travel. Even the last city should differ from the first. Two consecutive cities in the route should also be different. So you need to check these conditions for the given routes too.

You will be given the list of all cities and all roads between them with their lengths. All roads are one-way. Also you will be given the list of all travel routes that Chef plans. For each route you should check whether it is correct and find its length in this case.

-----Input-----

The first line contains positive integer N, the number of cities. The second line contains space separated list of N strings, city names. All city names are distinct.

The third line contains non-negative integer M, the number of available roads. Each of the next M lines describes one road and contains names C1 and C2 of two cities followed by the positive integer D, the length of the one-way road that connects C1 with C2. It is guaranteed that C1 and C2 will be correct names of two different cities from the list of N cities given in the second line of the input file. For each pair of different cities there is at most one road in each direction and each road will be described exactly once in the input file.

Next line contains positive integer T, the number of travel routes planned by the Chef. Each of the next T lines contains positive integer K followed by K strings, names of cities of the current route. Cities are given in order in which Chef will visit them during his travel.

All strings in the input file composed only of lowercase, uppercase letters of the English alphabet and hyphens. Each string is non-empty and has length at most 20. If some line of the input file contains more then one element than consecutive elements of this line are separated by exactly one space. Each line of the input file has no leading or trailing spaces.

-----Output-----
For each travel route from the input file output a single line containing word ERROR if the route is incorrect and its length otherwise.

-----Constraints-----

1 <= N <= 50

0 <= M <= N * (N - 1)

1 <= D <= 20000

1 <= T <= 50

1 <= K <= 50

1 <= length of each string <= 20

-----Example-----
Input:
5
Donetsk Kiev New-York Miami Hollywood
9
Donetsk Kiev 560
Kiev New-York 7507
New-York Miami 1764
Miami Hollywood 28
Hollywood Miami 30
Miami New-York 1764
Kiev Donetsk 550
Hollywood New-York 1736
New-York Hollywood 1738
13
5 Donetsk Kiev New-York Miami Hollywood
5 Hollywood Miami New-York Kiev Donetsk
3 Donetsk Kiev Donetsk
2 Kyiv New-York
3 New-York Hollywood Miami
2 New-York Miami
3 Hollywood New-York Miami
4 Donetsk Kiev Miami Hollywood
2 Donetsk Hollywood
1 Donetsk
2 Mumbai Deli
6 Donetsk Kiev New-York Miami Hollywood New-York
2 Miami Miami

Output:
9859
ERROR
ERROR
ERROR
1768
1764
3500
ERROR
ERROR
0
ERROR
ERROR
ERROR

-----Explanation-----
The 2nd route is incorrect since there is no road from New-York to Kiev. Note however that inverse road from Kiev to New-York exists. 

The 3rd route is incorrect since the first city coincides with the last one. 

The 4th route is incorrect since there is no city with name Kyiv (Probably Chef means Kiev but he misspells this word). 

The 8th route is incorrect since there is no road from Miami to Kiev. 

The 9th route is incorrect since there is no road from Donetsk to  Hollywood. 

The 10th route is correct. Note that a route composed of exactly one city is always correct provided that city name is written correctly. 

The 11th route is incorrect since there is no cities with names Mumbai and Deli. (Probably Chef is not so good in geography :)) 

The 12th route is incorrect since city New-York is visited twice. 

Finally the 13th route is incorrect since we have equal consecutive cities.

Difficulty: MEDIUM
Tags: String algorithms

Sorting

Implementation

Complete search

Data structures
Skill types: Sorting

Data structures

Complete search

Starter code:

Solutions:
city_num = int(input())
li = list(map(str, input().split()))
road_num = int(input())
di = {}
for _ in range(road_num):
	(a, b, c) = list(map(str, input().split()))
	di.update({a + b: int(c)})
tr_n = int(input())
for _ in range(tr_n):
	ro_li = list(map(str, input().split()))
	ro_n = int(ro_li[0])
	ro_li.pop(0)
	dup_check = set(ro_li)
	ans = 0
	t = 0
	if ro_n == 1:
		if ro_li[0] not in li:
			t = 1
	for i in range(ro_n - 1):
		ro = ro_li[i] + ro_li[i + 1]
		if ro in di:
			ans += di[ro]
		else:
			t = 1
	if t != 1 and len(dup_check) == len(ro_li):
		print(ans)
	else:
		print('ERROR')


import math
n = int(input())
city = [i for i in input().split()]
m = int(input())
route = {}
for i in range(m):
	r = [x for x in input().split()]
	route[r[0], r[1]] = int(r[2])
t = int(input())
for i in range(t):
	cRoute = [x for x in input().split()]
	k = int(cRoute[0])
	cRoute = cRoute[1:]
	if not all([x in city for x in cRoute]):
		print('ERROR')
		continue
	if len(set(cRoute)) != len(cRoute):
		print('ERROR')
		continue
	ans = 0
	for i in range(k - 1):
		if (cRoute[i], cRoute[i + 1]) in route:
			ans += route[cRoute[i], cRoute[i + 1]]
		else:
			print('ERROR')
			break
	else:
		print(ans)


n = int(input())
l = list(map(str, input().split()))
base = {}
for i in range(int(input())):
	(c1, c2, d) = map(str, input().split())
	base[c1 + c2] = int(d)
for i in range(int(input())):
	plans = list(map(str, input().split()))
	k = int(plans[0])
	flag = True
	dist = 0
	if k == 1:
		if plans[1] not in l:
			flag = False
	for j in range(1, k):
		if plans[j] + plans[j + 1] in base:
			dist += base[plans[j] + plans[j + 1]]
		else:
			flag = False
	if flag and len(plans) == len(set(plans)):
		print(dist)
	else:
		print('ERROR')


import sys

def _r(*conv):
	r = [conv[i](x) for (i, x) in enumerate(input().strip().split(' '))]
	return r[0] if len(r) == 1 else r

def _ra(conv):
	return list(map(conv, input().strip().split(' ')))

def _rl():
	return list(input().strip())

def _rs():
	return input().strip()

def _a(k, *v):
	return all((x == k for x in v))

def _i(conv):
	for line in sys.stdin:
		yield conv(line)
n = _r(int)
lookup = dict([(x, i) for (i, x) in enumerate(_ra(str))])
g = [(set(), dict()) for _ in range(n)]
m = _r(int)
for _ in range(m):
	(c1, c2, d) = _r(str, str, int)
	i1 = lookup[c1]
	g[i1][0].add(c2)
	g[i1][1][c2] = d
t = _r(int)
for _ in range(t):
	k = _ra(str)[1:]
	failed = False
	if len(set(k)) != len(k):
		failed = True
	if not failed:
		if k[0] not in lookup:
			failed = True
		else:
			r = 0
			v = g[lookup[k[0]]]
			for i in range(1, len(k)):
				if k[i] not in v[0]:
					failed = True
					break
				r += v[1][k[i]]
				v = g[lookup[k[i]]]
			if not failed:
				print(r)
	if failed:
		print('ERROR')


def main():
	n = eval(input())
	city = input().split()
	m = eval(input())
	mapp = {}
	for c in city:
		mapp[c] = [0] * n
	while m:
		m -= 1
		road = input().split()
		temp = mapp[road[0]]
		temp[city.index(road[1])] = int(road[-1])
		mapp[road[0]] = temp
	t = eval(input())
	while t:
		t -= 1
		dist = 0
		v = [0] * n
		route = input().split()
		if route[0] == '1':
			if route[-1] in city:
				print(dist)
			else:
				print('ERROR')
		else:
			for r in range(1, int(route[0]) + 1):
				if route[r] not in city or v[city.index(route[r])]:
					dist = 'ERROR'
					break
				elif r > 1:
					if mapp[route[r - 1]][city.index(route[r])]:
						dist += mapp[route[r - 1]][city.index(route[r])]
					else:
						dist = 'ERROR'
						break
				v[city.index(route[r])] = 1
			print(dist)
main()


def main():
	n = eval(input())
	city = input().split()
	m = eval(input())
	mapp = {}
	for c in city:
		mapp[c] = [0] * n
	while m:
		m -= 1
		road = input().split()
		elem = mapp[road[0]]
		elem[city.index(road[1])] = int(road[2])
		mapp[road[0]] = elem
	itins = eval(input())
	while itins:
		itins -= 1
		route = input().split()
		total = 0
		v = [0] * n
		if route[0] == '1':
			if route[-1] in city:
				print(total)
			else:
				print('ERROR')
		else:
			for r in range(1, len(route)):
				if route[r] not in city or v[city.index(route[r])]:
					total = 'ERROR'
					break
				elif r > 1:
					if mapp[route[r - 1]][city.index(route[r])]:
						total += mapp[route[r - 1]][city.index(route[r])]
					else:
						total = 'ERROR'
						break
				v[city.index(route[r])] = 1
			print(total)
main()


locations = int(input())
locations_list = input().split()
roads = int(input())
roads_dict = {}
for i in range(roads):
	(a, b, dist) = input().split()
	if a in locations_list and b in locations_list:
		roads_dict[a, b] = int(dist)
tests = int(input())
for i in range(tests):
	(length, *route) = input().split()
	length = int(length)
	ans = 0
	if len(set(route)) != length or route[0] not in locations_list:
		ans = 'ERROR'
	else:
		for j in range(length - 1):
			if (route[j], route[j + 1]) in roads_dict:
				ans += roads_dict[route[j], route[j + 1]]
			else:
				ans = 'ERROR'
				break
	print(ans)


import math
alf = 'abcdefghijklmnopqrstuvwxyz'
mod = 1000000007

def createDic(nums):
	dic = dict()
	for i in nums:
		if not i in dic:
			dic[i] = 1
		else:
			dic[i] += 1
	return dic

def subarray_sum_max(nums):
	array = []
	suma_parcial = 0
	max_sum = 0
	index = 0
	se_refresco = True
	for i in range(len(nums)):
		suma_parcial += nums[i]
		if max_sum < suma_parcial:
			if se_refresco:
				array = []
				se_refresco = False
				index = i
			max_sum = suma_parcial
		if suma_parcial < 0:
			suma_parcial = 0
			se_refresco = True
		elif not se_refresco:
			array.append(nums[i])
	return (array, index, max_sum)

def particiones(nums, index, array):
	if index == len(nums):
		count = 0
	else:
		for i in array:
			i.append(nums[index])
			particiones(nums, index + 1, array)
			i.pop(len(i) - 1)
		array.append([])
		array[len(array) - 1].append(nums[index])
		particiones(nums, index + 1, array)
		array.pop(len(array) - 1)

def busqueda_binaria(nums, x):
	izq = 0
	der = len(nums) - 1
	while izq <= der:
		medio = int((izq + der) / 2)
		if nums[medio] == x:
			return medio
		elif nums[medio] > x:
			der = medio - 1
		else:
			izq = medio + 1
	return -1

def solve():
	n = int(input())
	names = list(map(str, input().split()))
	m = int(input())
	dic = dict()
	for i in range(m):
		(c1, c2, dist) = map(str, input().split())
		dic[c1, c2] = int(dist)
	t = int(input())
	for i in range(t):
		array = list(map(str, input().split()))
		array_aux = []
		for j in range(1, len(array)):
			array_aux.append(array[j])
		dic_aux = createDic(array_aux)
		error = False
		for k in dic_aux:
			if dic_aux[k] != 1:
				print('ERROR')
				error = True
				break
		if error:
			continue
		pincha = True
		for q in dic_aux:
			pincha = False
			for p in names:
				if p == q:
					pincha = True
					break
			if not pincha:
				print('ERROR')
				error = True
				break
		if error:
			continue
		if len(array_aux) == 1:
			print(0)
			continue
		suma = 0
		for i in range(1, len(array_aux)):
			if not (array_aux[i - 1], array_aux[i]) in dic:
				print('ERROR')
				error = True
				break
			suma += dic[array_aux[i - 1], array_aux[i]]
		if error:
			continue
		print(suma)
test = 1
while test != 0:
	solve()
	test -= 1


input()
graph = {city: dict() for city in input().split()}

def traverseRoute(route):
	(visited, distance) = (set(), 0)
	if route[0] not in graph:
		return 'ERROR'
	visited.add(route[0])
	for index in range(1, len(route)):
		(source, target) = (route[index - 1], route[index])
		if target not in graph or target in visited or target not in graph[source]:
			return 'ERROR'
		distance += graph[source][target]
		visited.add(target)
	return distance
for e in range(int(input())):
	(source, target, cost) = input().split()
	graph[source][target] = int(cost)
for r in range(int(input())):
	print('{}'.format(traverseRoute(input().split()[1:])))


import math
N = int(input())
city = [x for x in input().split()]
M = int(input())
Route = {}
for m in range(M):
	r = [x for x in input().split()]
	Route[r[0], r[1]] = int(r[2])
T = int(input())
for t in range(T):
	cr = [x for x in input().split()]
	K = int(cr[0])
	cr = cr[1:]
	if not all([x in city for x in cr]):
		print('ERROR')
		continue
	if len(set(cr)) != len(cr):
		print('ERROR')
		continue
	count = 0
	for i in range(K - 1):
		if (cr[i], cr[i + 1]) in Route:
			count += Route[cr[i], cr[i + 1]]
		else:
			print('ERROR')
			break
	else:
		print(count)


nCities = int(input())
cities = input().split(' ')
nRoads = int(input())
Roads = {}
for i in range(nRoads):
	x = input().split(' ')
	Roads[' '.join(x[:2])] = int(x[2])
nRoutes = int(input())
for i in range(nRoutes):
	distance = 0
	route = input().split(' ')
	flag = True
	for i in route[1:]:
		if i not in cities:
			print('ERROR')
			flag = False
			break
	if flag:
		if int(route[0]) == len(set(route[1:])):
			for i in range(1, len(route) - 1):
				road = ' '.join(route[i:i + 2])
				if road in Roads:
					distance += Roads[road]
				else:
					print('ERROR')
					flag = False
					break
			if flag:
				print(distance)
		else:
			print('ERROR')


n = int(input())
cities = input().split()
m = int(input())
routes = []
for i in range(m):
	inp = input().split()
	routes.append(inp)
visited = []
for _ in range(int(input())):
	distance = flag = 0
	visited.clear()
	inp = input().split()
	k = int(inp[0])
	for i in range(1, k + 1):
		if inp[i] not in cities or inp[i] in visited:
			print('ERROR')
			flag = 1
			break
		visited.append(inp[i])
	if flag:
		continue
	for i in range(1, k):
		for j in routes:
			if j[0] == inp[i] and j[1] == inp[i + 1]:
				distance += int(j[2])
				break
		else:
			print('ERROR')
			flag = 1
			break
	if flag:
		continue
	print(distance)


n = int(input())
c = list(map(str, input().split()))
m = int(input())
d = dict()
for i in range(m):
	string = input().split()
	d[string[0], string[1]] = int(string[2])
t = int(input())
visited = []
for i in range(t):
	r = list(map(str, input().split(' ')))
	k = int(r[0])
	visited.clear()
	distance = 0
	flag = 0
	for i in range(1, k + 1):
		if r[i] in visited or r[i] not in c:
			print('ERROR')
			flag = 1
			break
		else:
			visited.append(r[i])
	if flag:
		continue
	for i in range(k - 1):
		if (visited[i], visited[i + 1]) in d:
			distance += d[visited[i], visited[i + 1]]
		else:
			print('ERROR')
			break
	else:
		print(distance)


import math
N = int(input())
city = [x for x in input().split()]
M = int(input())
route = {}
for m in range(M):
	r = [x for x in input().split()]
	route[r[0], r[1]] = int(r[2])
T = int(input())
for t in range(T):
	cur_route = [x for x in input().split()]
	K = int(cur_route[0])
	cur_route = cur_route[1:]
	if not all([x in city for x in cur_route]):
		print('ERROR')
		continue
	if len(set(cur_route)) != len(cur_route):
		print('ERROR')
		continue
	ans = 0
	for i in range(K - 1):
		if (cur_route[i], cur_route[i + 1]) in route:
			ans += route[cur_route[i], cur_route[i + 1]]
		else:
			print('ERROR')
			break
	else:
		print(ans)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	return input().strip()

def invr():
	return map(int, input().split())

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))
ans = []
N = inp()
cities = insr().split()
graph = {}
dist = {}
for _ in range(inp()):
	(s, d, l) = insr().split()
	if s in graph:
		graph[s].append(d)
		dist[s].append(int(l))
	else:
		graph[s] = [d]
		dist[s] = [int(l)]
k = inp()
for _ in range(k):
	route = insr().split()[1:]
	an = 0
	if len(route) == 1:
		if route[0] in cities:
			ans.append(0)
		else:
			ans.append('ERROR')
		continue
	if len(set(route)) != len(route):
		ans.append('ERROR')
		continue
	for i in range(len(route) - 1):
		if route[i] in graph and route[i + 1] in graph[route[i]]:
			an += dist[route[i]][graph[route[i]].index(route[i + 1])]
		else:
			an = -1
			break
	ans.append('ERROR' if an == -1 else an)
outplt(ans)


def check_city(cities, travel):
	for city in travel:
		if city not in cities:
			return False
	return True

def check_repeat(travel):
	travel_ = set(travel)
	if len(travel_) != len(travel):
		return True
	return False

def check_path(routes, distance, travel):
	n_city = travel[0]
	for i in range(n_city - 1):
		if [travel[i + 1], travel[i + 2]] not in routes:
			return False
	return True

def calc_dist(routes, distance, travel):
	n_city = travel[0]
	total_dist = 0
	for i in range(n_city - 1):
		index = routes.index([travel[i + 1], travel[i + 2]])
		total_dist += distance[index]
	return total_dist
n_city = int(input())
cities = list(input().split(' '))
n_route = int(input())
routes = list()
distance = list()
for i in range(n_route):
	route = list(input().split(' '))
	route[-1] = int(route[-1])
	distance.append(route[-1])
	route.pop()
	routes.append(route)
travel_n = int(input())
for i in range(travel_n):
	travel = list(input().split(' '))
	travel[0] = int(travel[0])
	value1 = check_city(cities, travel[1:])
	value2 = check_repeat(travel[1:])
	value3 = check_path(routes, distance, travel)
	if value1 == False or value2 == True or value3 == False:
		print('ERROR')
	else:
		print(calc_dist(routes, distance, travel))


n = int(input())
s = list(map(str, input().split()))
m = int(input())
dic = {}
for i in range(m):
	(a, b, c) = list(map(str, input().split()))
	c = int(c)
	dic[a, b] = c
t = int(input())
for i in range(t):
	x = list(map(str, input().split()))
	y = len(x)
	if int(x[0]) == 1 and x[1] in s:
		print('0')
	elif int(x[0]) == 1:
		print('ERROR')
	elif x[1] == x[y - 1]:
		print('ERROR')
	elif int(x[0]) > n:
		print('ERROR')
	else:
		flag = 1
		ans = 0
		dic2 = {}
		for j in range(1, len(x)):
			if x[j] in dic2:
				dic2[x[j]] += 1
			else:
				dic2[x[j]] = 1
		for j in dic2:
			if dic2[j] > 1:
				flag = 0
				break
		if flag == 1:
			for j in range(1, len(x) - 1):
				if (x[j], x[j + 1]) in dic:
					ans += dic[x[j], x[j + 1]]
				else:
					flag = 0
					break
		if flag == 0:
			print('ERROR')
		else:
			print(ans)


total_cities = int(input())
cities = list(map(str, input().split(' ')))
routes = int(input())
d = {}
for i in range(routes):
	(a, b, c) = input().split(' ')
	d[a + b] = int(c)
travel_plans = int(input())
for i in range(travel_plans):
	li = list(map(str, input().split(' ')))
	planned = int(li[0])
	flag = True
	distance = 0
	if planned == 1:
		if li[1] not in cities:
			flag = False
	for i in range(1, planned):
		if li[i] + li[i + 1] in d:
			distance += d[li[i] + li[i + 1]]
		else:
			flag = False
	if flag and len(li) == len(set(li)):
		print(distance)
	else:
		print('ERROR')


n = int(input())
city = list(input().split())
m = int(input())
r = []
l = []
tc = []
for i in range(m):
	(a, b, c) = input().split()
	r.append([a, b])
	l.append(int(c))
for i in range(int(input())):
	s = input()
	tc.append(list(s[2:].split()))
for i in tc:
	t = True
	for j in i:
		if j not in city:
			t = False
			break
	if t:
		for j in i:
			if i.count(j) == 1:
				pass
			else:
				t = False
				break
		if t:
			s = 0
			for j in range(len(i) - 1):
				if [i[j], i[j + 1]] in r:
					s = s + l[r.index([i[j], i[j + 1]])]
				else:
					t = False
					break
			if t:
				print(s)
			else:
				print('ERROR')
		else:
			print('ERROR')
	else:
		print('ERROR')


def spell_check(city, cur_route):
	k = int(cur_route[0])
	cur_route = cur_route[1:]
	if not all([x in city for x in cur_route]):
		return 0
	return 1

def duplicate_check(cur_route):
	cur_route = cur_route[1:]
	if len(set(cur_route)) != len(cur_route):
		return 0
	return 1
n = int(input())
city = set(list(map(str, input().split())))
m = int(input())
route = {}
for i in range(m):
	r = [x for x in input().split()]
	route[r[0], r[1]] = int(r[2])
t = int(input())
for i in range(t):
	cur_route = [x for x in input().split()]
	k = int(cur_route[0])
	if not spell_check(city, cur_route) or not duplicate_check(cur_route):
		print('ERROR')
		continue
	ans = 0
	for i in range(1, k):
		if (cur_route[i], cur_route[i + 1]) in route:
			ans += route[cur_route[i], cur_route[i + 1]]
		else:
			print('ERROR')
			break
	else:
		print(ans)


n = int(input())
l = list(map(str, input().split()))
m = int(input())
root = {}
for i in range(m):
	(c1, c2, d) = map(str, input().split())
	root[c1 + c2] = int(d)
t = int(input())
for i in range(t):
	plans = list(map(str, input().split()))
	k = int(plans[0])
	ans = True
	distance = 0
	if k == 1:
		if plans[1] not in l:
			ans = False
	for j in range(1, k):
		if plans[j] + plans[j + 1] in root:
			distance += root[plans[j] + plans[j + 1]]
		else:
			ans = False
	if ans and len(plans) == len(set(plans)):
		print(distance)
	else:
		print('ERROR')


n = int(input())
cities = input().strip().split(' ')
citd = dict()
for cit in cities:
	citd[cit] = True
m = int(input())
roads = dict()
for i in range(0, m):
	temp = input().strip().split(' ')
	roads[temp[0] + ':' + temp[1]] = int(temp[2])
t = int(input())
for i in range(0, t):
	li = input().strip().split(' ')
	temp = set(li)
	cost = 0
	if len(li) != len(temp):
		print('ERROR')
	elif li[0] == '1' and citd.get(li[1], False):
		print(0)
	elif li[0] == '1' and (not citd.get(li[1], False)):
		print('ERROR')
	else:
		for j in range(2, int(li[0]) + 1):
			if roads.get(li[j - 1] + ':' + li[j], False):
				cost += roads[li[j - 1] + ':' + li[j]]
			else:
				cost = -1
				break
		if cost != -1:
			print(cost)
		else:
			print('ERROR')