Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chefland is a country with $N$ cities (numbered $1$ through $N$) connected by $M$ bidirectional roads. Chef is on a mission to spread a secret recipe of a Rogan Josh dish. Chef has a sequence $A_{1}, A_{2}, \ldots, A_{K}$ and he must visit cities in the following way: he starts in the city $A_{1}$, travels to the city $A_{2}$, then travels from there to the city $A_{3}$ and so on until he reaches the city $A_{K}$. Note that a city may appear in $A$ multiple times, but $A_{i} \neq A_{i+1}$ for each valid $i$. When travelling between two cities, Chef always follows one of the shortest paths between them (but not necessarily the same one if he travels between them again).

The government is trying to track which cities are targeted by Chef. However, they do not know the sequence $A$. Instead, they have tracked Chef's movement as a sequence $B_{1}, B_{2}, \ldots, B_{L}$ of cities visited by Chef during his mission. Formally, $B_{1} = A_{1}$ is the city where Chef starts, then for each valid $i$, he moves from the city $B_{i}$ to the city $B_{i+1}$ using the direct road between them and finally, he ends his mission in the city $B_{L} = A_{K}$; Chef's sequence $A$ is a subsequence of $B$, since the sequence $B$ also contains all shortest paths which Chef followed. It is guaranteed that there is a direct road between cities $B_{i}$ and $B_{i+1}$ for each valid $i$.

Help the government of Chefland find the minimum possible number of targeted cities, i.e. the minimum possible value of $K$ for a sequence $A$ that corresponds to the given sequence $B$, or determine that no such sequence $A$ exists.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains three space-separated integers $N$, $M$ and $L$.
The second line contains $L$ space-separated integers $B_{1}, B_{2}, \ldots, B_{L}$.
Each of the following $M$ lines contains three space-separated integers $u$, $v$ and $w$ describing a road between cities $u$ and $v$ with length $w$.

------  Output ------
For each test case, print a single line containing one integer ― the minimum possible $K$, or $-1$ if a valid sequence $A$ does not exist.

------  Constraints ------
$1 ≤ T ≤ 10$
$2 ≤ N ≤ 200$
$1 ≤ M ≤ N \cdot (N-1)/2$
$2 ≤ L ≤ 10,000$
$1 ≤ u, v ≤ N$
$u \neq v$
$1 ≤ w ≤ 10^{6}$
there is at most one direct road between each pair of cities
for each valid $i$, there is a direct road between cities $B_{i}$ and $B_{i+1}$

------  Subtasks ------
Subtask #1 (50 points): $w = 1$

Subtask #2 (50 points): original constraints

----- Sample Input 1 ------ 
3

3 3 6

1 2 3 1 2 3

1 2 1

2 3 1

3 1 1

4 4 9

1 2 3 4 1 2 3 4 1

1 2 1

2 3 1

3 4 1

4 1 1

3 3 2

1 2

1 2 3

2 3 1

3 1 1
----- Sample Output 1 ------ 
6

5

-1

Source: codechef | Difficulty: VERY_HARD
Tags: Greedy algorithms

Graph algorithms

Data structures

Shortest paths


Solutions:
import math, sys
from collections import defaultdict, deque
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

def I():
	return int(sys.stdin.readline())

def In():
	return map(int, sys.stdin.readline().split())

def Sn():
	return sys.stdin.readline().strip()
from heapq import heappop, heappush

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return -1

def djk(n, gp, st):
	dist = [P] * n
	pq = [(0, st)]
	dist[st] = 0
	while pq:
		(val, u) = heappop(pq)
		for (v, cost) in gp[u]:
			if dist[v] > dist[u] + cost:
				dist[v] = dist[u] + cost
				heappush(pq, (dist[v], v))
	return dist

def main():
	try:
		(n, nq, m) = In()
		l = list(In())
		gp = defaultdict(list)
		dp = [[P for i in range(n)] for j in range(n)]
		for i in range(nq):
			(a, b, c) = In()
			a -= 1
			b -= 1
			gp[a].append((b, c))
			gp[b].append((a, c))
			dp[a][b] = c
			dp[b][a] = c
		dp1 = [djk(n, gp, i) for i in range(n)]
		for i in range(n):
			dp[i][i] = 0
		ans = 1
		i = 0
		j = 0
		ok = True
		while i < m - 1:
			while j + 1 < m:
				dis = 0
				for k in range(i, j + 1):
					dis += dp[l[k] - 1][l[k + 1] - 1]
				if dis > dp1[l[i] - 1][l[j + 1] - 1]:
					break
				j += 1
			if i == j:
				ok = False
				break
			i = j
			ans += 1
		print(ans) if ok else print(-1)
	except:
		pass
M = 998244353
P = 1000000007
for _ in range(I()):
	main()


import heapq

def dijkstra(src):
	dist = [100000000] * n
	dist[src] = 0
	vis = [0] * n
	s = []
	heapq.heapify(s)
	heapq.heappush(s, (0, src))
	while len(s) != 0:
		(wei, x) = heapq.heappop(s)
		if vis[x] == 1:
			continue
		vis[x] = 1
		for i in g[x]:
			w = g[x][i]
			if dist[x] + w < dist[i]:
				dist[i] = dist[x] + w
				heapq.heappush(s, (dist[i], i))
	return dist
for i in range(int(input())):
	(n, m, l) = map(int, input().split())
	B = list(map(int, input().split()))
	g = [{} for i in range(n)]
	for j in range(m):
		(u, v, w) = map(int, input().split())
		g[u - 1][v - 1] = w
		g[v - 1][u - 1] = w
	d = []
	for i in range(n):
		d.append(dijkstra(i))
	ans = 1
	j = 1
	k = d[B[0] - 1][B[1] - 1]
	ind = B[0] - 1
	while j < l - 1:
		if d[B[j] - 1][B[j + 1] - 1] + k != d[ind][B[j + 1] - 1]:
			ans += 1
			k = d[B[j] - 1][B[j + 1] - 1]
			ind = B[j] - 1
		else:
			k += d[B[j] - 1][B[j + 1] - 1]
		j += 1
	if l == 2:
		print(-1)
	else:
		print(ans + 1)


INF = 10 ** 6 * 200
II = lambda : [int(x) for x in input().split()]
from collections import defaultdict
from functools import reduce

def solve(N, L, B, G, dists):
	for k in range(N):
		for i in range(N):
			a = dists[i][k]
			for j in range(i + 1, N):
				if a < dists[i][j] and a + dists[k][j] < dists[i][j]:
					dists[i][j] = dists[j][i] = a + dists[k][j]
	A = [B[0]]
	i_dists = [0]
	starts = B[0]
	dist = 0
	for i in range(1, L):
		dist += G[B[i - 1] - 1][B[i] - 1]
		if dist > dists[starts - 1][B[i] - 1]:
			A.append(B[i - 1])
			starts = B[i - 1]
			i_dists.append(dist - G[B[i - 1] - 1][B[i] - 1])
			dist = dists[B[i - 1] - 1][B[i] - 1]
	A.append(B[-1])
	i_dists.append(dist)
	for i in range(1, len(A)):
		if A[i] == A[i - 1] or i_dists[i] > dists[A[i - 1] - 1][A[i] - 1] or i_dists[i] >= INF:
			return -1
	return len(A)
T = int(input())
for _ in range(T):
	(N, M, L) = II()
	B = II()
	G = [[INF] * N for _ in range(N)]
	D = [[INF] * N for _ in range(N)]
	for i in range(N):
		G[i][i] = D[i][i] = 0
	for _ in range(M):
		(u, v, w) = II()
		G[u - 1][v - 1] = D[u - 1][v - 1] = w
		G[v - 1][u - 1] = D[v - 1][u - 1] = w
	res = solve(N, L, B, G, D)
	print(res)