#nullable enable using System.Numerics; #region var _input = Array.Empty(); var _iter = 0; string String() { while (_iter >= _input.Length) (_input, _iter) = (Console.ReadLine()!.Split(' '), 0); return _input[_iter++]; } T I() where T : IParsable => T.Parse(String(), null); #endregion var n = I(); var m = I(); var oez = Range(m, () => (I() - 1, I() - 1)); var k = I(); var iwiz = new bool[n]; for (var i = 0; i < k; i++) iwiz[I() - 1] = true; var edges = new List<(int, int)>(); for (var i = 0; i < m; i++) { var (u, v) = oez[i]; for (var _i = 0; _i < 2; _i++) { if (iwiz[v]) { for (var t = 0; t <= 3; t++) { edges.Add((u + t * n, v + (t + 1) * n)); } } else { for (var t = 0; t <= 4; t++) { edges.Add((u + t * n, v)); } } (u, v) = (v, u); } } var dz = new int[edges.Count]; dz.AsSpan().Fill(1); var sg = new StaticGraph(edges, n * 5, true); var max = int.MaxValue / 2; var spz = Distances(new(){ StaticGraph = sg }, 0, dz, max); var ans = max; for (var i = 0; i <= 4; i++) ans = Math.Min(ans, spz[n - 1 + i * n].d); if (ans == max) ans = -1; Console.WriteLine(ans); static T[] Range(int n, Func F) => Enumerable.Range(0, n).Select(_ => F()).ToArray(); static Span<(T d, int prevE, int prevV)> Distances( Graph graph, int start, IReadOnlyList distances, T infinity ) where T : IComparable, INumber { var g = graph.StaticGraph; var res = new (T, int, int)[g.N].AsSpan(); for (var i = 0; i < res.Length; i++) res[i] = (infinity, -1, -1); var determined = new bool[g.N].AsSpan(); var q = new PriorityQueue(); q.Enqueue(start, res[start].Item1 = T.AdditiveIdentity); while (q.Count > 0) { var v = q.Dequeue(); if (determined[v]) continue; determined[v] = true; var adjacencies = g.Adjacencies(v); foreach (var (next, ei) in adjacencies) { var d = res[v].Item1 + distances[ei]; if (res[next].Item1.CompareTo(d) <= 0) continue; res[next] = (d, v, ei); q.Enqueue(next, d); } } return res; } class StaticGraph { public int N { get; } public bool Directed { get; } public ReadOnlySpan<(int next, int edgeIndex)> Adjacencies(int of) => _adjacencyList.Span[of].Span; public ReadOnlySpan<(int Ab, int Ad)> Edges => _edges.Span; readonly ReadOnlyMemory> _adjacencyList; readonly ReadOnlyMemory<(int Ab, int Ad)> _edges; public StaticGraph(IReadOnlyList<(int, int)> edges, int verticals, bool directed) { (N, Directed) = (verticals, directed); var al = new List<(int, int)>[verticals]; for (var i = 0; i < verticals; i++) al[i] = new(); _edges = edges.ToArray(); for (var i = 0; i < edges.Count; i++) { var (ab, ad) = edges[i]; al[ab].Add((ad, i)); if (!Directed) al[ad].Add((ab, i)); } var ala = new ReadOnlyMemory<(int, int)>[verticals]; var dataMemory = new (int, int)[directed ? edges.Count : edges.Count * 2].AsMemory(); var dataSpan = dataMemory.Span; var k = 0; for (var i = 0; i < verticals; i++) { var length = al[i].Count; for (var j = 0; j < length; j++) dataSpan[k + j] = al[i][j]; ala[i] = dataMemory.Slice(k, length); k += length; } _adjacencyList = ala; } } class Graph { public required StaticGraph StaticGraph { get; init; } }