using AtCoder;
using AtCoder.Internal;
using HatoLibrary;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.CompilerServices;
class Program
{
    static string ReadLine() => Console.ReadLine().Trim();
    static int ReadInt() => int.Parse(ReadLine());
    static long ReadLong() => long.Parse(ReadLine());
    static int[] ReadIntArray() { string str = ReadLine(); return str != "" ? str.Split().Select(_ => int.Parse(_)).ToArray() : new int[0]; }
    static long[] ReadLongArray() { string str = ReadLine(); return str != "" ? str.Split().Select(_ => long.Parse(_)).ToArray() : new long[0]; }

    static (int a, int b) ReadInt2() { int[] vs = ReadIntArray(); return (a: vs[0], b: vs[1]); }
    static (int a, int b, int c) ReadInt3() { int[] vs = ReadIntArray(); return (a: vs[0], b: vs[1], c: vs[2]); }
    static (int a, int b, int c, int d) ReadInt4() { int[] vs = ReadIntArray(); return (a: vs[0], b: vs[1], c: vs[2], d: vs[3]); }
    static (long a, long b) ReadLong2() { long[] vs = ReadLongArray(); return (a: vs[0], b: vs[1]); }
    static (long a, long b, long c) ReadLong3() { long[] vs = ReadLongArray(); return (a: vs[0], b: vs[1], c: vs[2]); }
    static (long a, long b, long c, long d) ReadLong4() { long[] vs = ReadLongArray(); return (a: vs[0], b: vs[1], c: vs[2], d: vs[3]); }

    static void Main()
    {
        SourceExpander.Expander.Expand();

        (int N, int M) = ReadInt2();

        Graph g = new Graph(N);

        int[] A = new int[M];
        int[] B = new int[M];
        for (int i = 0; i < M; i++)
        {
            (int a, int b) = ReadInt2();
            a--;
            b--;
            g.AddEdge(a, b);
            g.AddEdge(b, a);
            A[i] = a; 
            B[i] = b;
        }

        int L = ReadInt();
        int[] starts = new int[L];
        long[] dists = new long[L];
        for (int i = 0; i < L; i++)
        {
            (int a, int k) = ReadInt2();
            a--;
            starts[i] = a;
            dists[i] = k;
        }
        bool[] isNG = g.IsWithinDistance(starts, dists);

        Graph g2 = new Graph(N);
        for (int i = 0; i < M; i++)
        {
            int a = A[i];
            int b = B[i];
            if (!isNG[a] && !isNG[b])
            {
                g2.AddEdge(a, b);
                g2.AddEdge(b, a);
            }
        }
        var D = g2.Dijkstra(0);
        if (D[N - 1] < long.MaxValue)
        {
            Console.WriteLine("Yes");
            Console.WriteLine(D[N - 1]);
        }
        else
            Console.WriteLine("No");
    }
}

#region Expanded by https://github.com/kzrnm/SourceExpander
namespace AtCoder{public class Dsu{public readonly int[]_ps;public Dsu(int n){_ps=new int[n];_ps.AsSpan().Fill(-1);}[MethodImpl(256)]public int Merge(int a,int b){int x=Leader(a),y=Leader(b);if(x==y)return x;if(-_ps[x]<-_ps[y])(x,y)=(y,x);_ps[x]+=_ps[y];_ps[y]=x;return x;}[MethodImpl(256)]public bool Same(int a,int b){return Leader(a)==Leader(b);}[MethodImpl(256)]public int Leader(int a){if(_ps[a]<0)return a;while(0<=_ps[_ps[a]]){(a,_ps[a])=(_ps[a],_ps[_ps[a]]);}return _ps[a];}[MethodImpl(256)]public int Size(int a){return-_ps[Leader(a)];}[MethodImpl(256)]public int[][]Groups(){int n=_ps.Length;int[]leaderBuf=new int[n];int[]id=new int[n];var resultList=new SimpleList<int[]>(n);for(int i=0;i<leaderBuf.Length;i++){leaderBuf[i]=Leader(i);if(i==leaderBuf[i]){id[i]=resultList.Count;resultList.Add(new int[-_ps[i]]);}}var result=resultList.ToArray();int[]ind=new int[result.Length];for(int i=0;i<leaderBuf.Length;i++){var leaderID=id[leaderBuf[i]];result[leaderID][ind[leaderID]]=i;ind[leaderID]++;}return result;}}}
namespace AtCoder.Internal{public class Csr<TEdge>:IEnumerable<(int from,TEdge edge)>{public readonly int[]Start;public readonly TEdge[]EList;public Csr(int n,ICollection<(int from,TEdge e)>edges){Start=new int[n+1];EList=new TEdge[edges.Count];foreach(var(from,_)in edges){Start[from+1]++;}for(int i=1;i<=n;i++){Start[i]+=Start[i-1];}var counter=(int[])Start.Clone();foreach(var(from,e)in edges){EList[counter[from]++]=e;}}public Enumerator GetEnumerator()=>new Enumerator(this);IEnumerator<(int from,TEdge edge)>IEnumerable<(int from,TEdge edge)>.GetEnumerator()=>GetEnumerator();IEnumerator IEnumerable.GetEnumerator()=>GetEnumerator();public struct Enumerator:IEnumerator<(int from,TEdge edge)>{public Enumerator(Csr<TEdge>g){_g=g;index=-1;start=0;}private readonly Csr<TEdge>_g;private int index;private int start;public(int from,TEdge edge)Current=>(start,_g.EList[index]);object IEnumerator.Current=>Current;[MethodImpl(256)]public bool MoveNext(){if( ++index<_g.Start[start+1])return true;return MoveNextStart();}private bool MoveNextStart(){for( ++start;start+1<_g.Start.Length;++start)if(index<_g.Start[start+1])return true;return false;}public void Reset(){index=-1;start=0;}void IDisposable.Dispose(){}}}}
namespace AtCoder{public class SccGraph{internal readonly int _n;public readonly SimpleList<(int from,int to)>edges;public SccGraph(int n){_n=n;edges=new SimpleList<(int from,int to)>();}[MethodImpl(256)]public void AddEdge(int from,int to){edges.Add((from,to));}[MethodImpl(256)]public(int groupNum,int[]ids)SccIDs(){var g=new Csr<int>(_n,edges);int nowOrd=0;int groupNum=0;var visited=new Stack<int>(_n);var low=new int[_n];var ord=Enumerable.Repeat(-1,_n).ToArray();var ids=new int[_n];for(int i=0;i<ord.Length;i++){if(ord[i]==-1){DFS(i);}}foreach(ref var x in ids.AsSpan()){x=groupNum-1-x;}return(groupNum,ids);void DFS(int v){var stack=new Stack<(int v,int childIndex)>();stack.Push((v,g.Start[v]));DFS:while(stack.Count>0){int ci;(v,ci)=stack.Pop();if(ci==g.Start[v]){low[v]=nowOrd;ord[v]=nowOrd++;visited.Push(v);}else if(ci<0){ci=-ci;int to=g.EList[ci-1];low[v]=Math.Min(low[v],low[to]);}for(;ci<g.Start[v+1];ci++){int to=g.EList[ci];if(ord[to]==-1){stack.Push((v,-(ci+1)));stack.Push((to,g.Start[to]));goto DFS;}else{low[v]=Math.Min(low[v],ord[to]);}}if(low[v]==ord[v]){while(true){int u=visited.Pop();ord[u]=_n;ids[u]=groupNum;if(u==v){break;}}groupNum++;}}}}[MethodImpl(256)]public int[][]Scc(){var(groupNum,ids)=SccIDs();var groups=new int[groupNum][];var counts=new int[groupNum];var seen=new int[groupNum];foreach(var x in ids)counts[x]++;for(int i=0;i<groupNum;i++)groups[i]=new int[counts[i]];for(int i=0;i<ids.Length;i++)groups[ids[i]][seen[ids[i]]++]=i;return groups;}}}
namespace AtCoder.Internal{public class SimpleList<T>:IList<T>,IReadOnlyList<T>{public T[]data;private const int DefaultCapacity=2;public SimpleList(){data=new T[DefaultCapacity];}public SimpleList(int capacity){data=new T[Math.Max(capacity,DefaultCapacity)];}public SimpleList(IEnumerable<T>collection){if(collection is ICollection<T>col){data=new T[col.Count];col.CopyTo(data,0);Count=col.Count;}else{data=new T[DefaultCapacity];foreach(var item in collection)Add(item);}}[MethodImpl(256)]public Memory<T>AsMemory()=>new Memory<T>(data,0,Count);[MethodImpl(256)]public Span<T>AsSpan()=>new Span<T>(data,0,Count);public ref T this[int index]{[MethodImpl(256)]get{if((uint)index>=(uint)Count)ThrowIndexOutOfRangeException();return ref data[index];}}public int Count{get;private set;}[MethodImpl(256)]public void Add(T item){if((uint)Count>=(uint)data.Length)Array.Resize(ref data,data.Length<<1);data[Count++]=item;}[MethodImpl(256)]public void RemoveLast(){if( --Count<0)ThrowIndexOutOfRangeException();}[MethodImpl(256)]public void RemoveLast(int size){if((Count-=size)<0)ThrowIndexOutOfRangeException();}[MethodImpl(256)]public SimpleList<T>Reverse(){Array.Reverse(data,0,Count);return this;}[MethodImpl(256)]public SimpleList<T>Reverse(int index,int count){Array.Reverse(data,index,count);return this;}[MethodImpl(256)]public SimpleList<T>Sort(){Array.Sort(data,0,Count);return this;}[MethodImpl(256)]public SimpleList<T>Sort(IComparer<T>comparer){Array.Sort(data,0,Count,comparer);return this;}[MethodImpl(256)]public SimpleList<T>Sort(int index,int count,IComparer<T>comparer){Array.Sort(data,index,count,comparer);return this;}[MethodImpl(256)]public void Clear()=>Count=0;[MethodImpl(256)]public bool Contains(T item)=>IndexOf(item)>=0;[MethodImpl(256)]public int IndexOf(T item)=>Array.IndexOf(data,item,0,Count);[MethodImpl(256)]public void CopyTo(T[]array,int arrayIndex)=>Array.Copy(data,0,array,arrayIndex,Count);[MethodImpl(256)]public T[]ToArray()=>AsSpan().ToArray();bool ICollection<T>.IsReadOnly=>false;T IList<T>.this[int index]{get=>data[index];set=>data[index]=value;}T IReadOnlyList<T>.this[int index]{get=>data[index];}void IList<T>.Insert(int index,T item)=>throw new NotSupportedException();bool ICollection<T>.Remove(T item)=>throw new NotSupportedException();void IList<T>.RemoveAt(int index)=>throw new NotSupportedException();IEnumerator IEnumerable.GetEnumerator()=>((IEnumerable<T>)this).GetEnumerator();IEnumerator<T>IEnumerable<T>.GetEnumerator(){for(int i=0;i<Count;i++)yield return data[i];}[MethodImpl(256)]public Span<T>.Enumerator GetEnumerator()=>AsSpan().GetEnumerator();private static void ThrowIndexOutOfRangeException()=>throw new IndexOutOfRangeException();}}
namespace AtCoder{public static class StlFunction{public struct NextPermutationEnumerator<T>:IEnumerator<T[]>,IEnumerable<T[]>where T:IComparable<T>{internal readonly IEnumerable<T>_orig;internal NextPermutationEnumerator(IEnumerable<T>orig){_orig=orig;Current=null;}public T[]Current{get;private set;}[MethodImpl(256)]public bool MoveNext(){if(Current==null){Current=_orig.ToArray();return true;}return NextPermutation(Current);}public void Reset()=>Current=null;object IEnumerator.Current=>Current;void IDisposable.Dispose(){}[MethodImpl(256)]public NextPermutationEnumerator<T>GetEnumerator()=>this;IEnumerator<T[]>IEnumerable<T[]>.GetEnumerator()=>this;IEnumerator IEnumerable.GetEnumerator()=>this;}[MethodImpl(256)]public static bool NextPermutation<T>(T[]array)where T:IComparable<T> =>NextPermutation(array.AsSpan());[MethodImpl(256)]public static bool NextPermutation<T>(Span<T>span)where T:IComparable<T>{int i;for(i=span.Length-2;i>=0;i--)if(span[i].CompareTo(span[i+1])<0)break;if(i<0)return false;int j;for(j=span.Length-1;j>=0;j--)if(span[i].CompareTo(span[j])<0)break;(span[i],span[j])=(span[j],span[i]);span.Slice(i+1,span.Length-i-1).Reverse();return true;}[MethodImpl(256)]public static NextPermutationEnumerator<T>Permutations<T>(IEnumerable<T>orig)where T:IComparable<T> =>new NextPermutationEnumerator<T>(orig);private struct DefaultComparer<T>:IComparer<T>where T:IComparable<T>{[MethodImpl(256)]public int Compare(T x,T y)=>x.CompareTo(y);}[MethodImpl(256)]public static int BinarySearch(int ok,int ng,Predicate<int>Ok){while(Math.Abs(ok-ng)>1){var m=(ok+ng)>>1;if(Ok(m))ok=m;else ng=m;}return ok;}[MethodImpl(256)]public static long BinarySearch(long ok,long ng,Predicate<long>Ok){while(Math.Abs(ok-ng)>1){var m=(ok+ng)>>1;if(Ok(m))ok=m;else ng=m;}return ok;}}}
namespace HatoLibrary { public class Graph { class Edge { public Edge(int next, long weight) { Next = next; Weight = weight; }  public int Next = 0; public long Weight = 0; }  int N = 0; List<Edge>[] Edges; public Graph(int n) { N = n; Edges = new List<Edge>[N]; for (int i = 0; i < N; i++) Edges[i] = new List<Edge>(); }  public void AddEdge(int from, int next, long w = 1) { Edges[from].Add(new Edge(next, w)); }  public List<(List<int> Blacks, List<int> Whites, Dictionary<int, int[]> LinkedList)> IsBipartiteGraph() { var rets = new List<(List<int> Blacks, List<int> Whites, Dictionary<int, int[]> LinkedList)>(); Dsu dsu = new Dsu(N); for (int i = 0; i < N; i++) { foreach (var e in Edges[i]) dsu.Merge(i, e.Next); }  int len = dsu.Groups().Length; int[][] groups = dsu.Groups(); int[] colors = new int[N]; foreach (var group in groups) { int start = group[0]; var ret = F(start); if (ret != null) { var linkedList = new Dictionary<int, int[]>(); foreach (var v in group) linkedList.Add(v, Edges[v].Select(_ => _.Next).ToArray()); rets.Add((Blacks: ret.Value.Blacks, Whites: ret.Value.Whites, LinkedList: linkedList)); } }  return rets; (List<int> Blacks, List<int> Whites)? F(int start) { List<int> blacks = new List<int>(); List<int> whites = new List<int>(); colors[start] = 1; blacks.Add(start); if (Dfs(start)) { return (Blacks: blacks, Whites: whites); } else { return null; }  bool Dfs(int cur) { foreach (var e in Edges[cur]) { int ncolor = colors[cur] == 1 ? -1 : 1; if (colors[e.Next] == 0) { colors[e.Next] = ncolor; if (ncolor == 1) blacks.Add(e.Next); else whites.Add(e.Next); bool ret = Dfs(e.Next); if (ret == false) return false; } else if (colors[e.Next] != ncolor) { return false; } }  return true; } } }  public long GetLongestValue(int start, int goal) { return GetLongestValue(start)[goal]; }  public long[] GetLongestValue(int start) { List<Edge>[] edges = new List<Edge>[N]; for (int cur = 0; cur < N; cur++) { edges[cur] = new List<Edge>(); foreach (var e in Edges[cur]) edges[cur].Add(new Edge(e.Next, -e.Weight)); }  long[] rets = BellmanFord(edges, start); for (int i = 0; i < N; i++) { if (rets[i] != long.MinValue) rets[i] *= -1; else rets[i] = long.MaxValue; }  return rets; }  public bool NegativeCycle(int start) { long[] dists = new long[N]; long inf = long.MaxValue; for (int i = 0; i < N; i++) dists[i] = inf; dists[start] = 0; int cnt = 0; while (cnt < N + 10) { bool updated = false; for (int cur = 0; cur < N; cur++) { if (dists[cur] == inf) continue; foreach (var e in Edges[cur]) { int next = e.Next; if (dists[next] > dists[cur] + e.Weight) { dists[next] = dists[cur] + e.Weight; updated = true; } } }  if (!updated) return false; cnt++; }  return true; }  public long[] BellmanFord(int start) { return BellmanFord(Edges, start); }  long[] BellmanFord(List<Edge>[] edges, int start) { long[] dists = new long[N]; long inf = long.MaxValue; for (int i = 0; i < N; i++) dists[i] = inf; dists[start] = 0; int cnt = 0; bool ok = false; while (cnt < N + 10) { bool updated = false; for (int cur = 0; cur < N; cur++) { if (dists[cur] == inf) continue; foreach (var e in edges[cur]) { int next = e.Next; if (dists[next] > dists[cur] + e.Weight) { dists[next] = dists[cur] + e.Weight; updated = true; } } }  if (!updated) { ok = true; break; }  cnt++; }  bool[] negatives = new bool[N]; if (!ok) { for (int i = 0; i < N; i++) { for (int cur = 0; cur < N; cur++) { if (dists[cur] == inf) continue; foreach (var e in edges[cur]) { int next = e.Next; if (dists[next] > dists[cur] + e.Weight) { dists[next] = dists[cur] + e.Weight; negatives[next] = true; }  if (negatives[cur]) negatives[next] = true; } } } }  for (int i = 0; i < N; i++) { if (negatives[i]) dists[i] = long.MinValue; }  return dists; }  public int[][] GetConnectedComponents() { AtCoder.Dsu dsu = new AtCoder.Dsu(N); for (int from = 0; from < N; from++) { foreach (var e in Edges[from]) dsu.Merge(from, e.Next); }  return dsu.Groups(); }  public bool IsPathGraph(int[] vertices, bool noCheck) { if (!IsTree(vertices, noCheck)) return false; foreach (int vertex in vertices) { if (Edges[vertex].Count >= 3) return false; }  return true; }  public bool IsPathGraph() { Dsu dsu = new Dsu(N); for (int i = 0; i < N; i++) { foreach (var e in Edges[i]) { int next = e.Next; if (!dsu.Same(i, next)) dsu.Merge(i, next); } }  var groups = dsu.Groups(); if (groups.Length != 1) return false; if (!IsTree(groups[0], true)) return false; foreach (int vertex in groups[0]) { if (Edges[vertex].Count >= 3) return false; }  return true; }  public bool IsTree(int[] vertices, bool noCheck) { long edgesCount = 0; foreach (int vertex in vertices) edgesCount += Edges[vertex].Count; edgesCount /= 2; if (vertices.Length - 1 != edgesCount) return false; if (!noCheck) { int start = vertices[0]; bool[] seen = new bool[N]; seen[start] = true; Queue<int> q = new Queue<int>(); q.Enqueue(start); while (q.Count > 0) { int cur = q.Dequeue(); foreach (var e in Edges[cur]) { int next = e.Next; if (seen[next]) continue; seen[next] = true; q.Enqueue(next); } }  foreach (int vertex in vertices) { if (!seen[vertex]) return false; } }  return true; }  public void DfsTree() { bool[] seen = new bool[N]; dfs(0); void dfs(int v) { if (seen[v]) return; seen[v] = true; foreach (var e in Edges[v]) { int next = e.Next; if (seen[next]) continue; Console.WriteLine($"{v + 1} => {next + 1}"); dfs(next); } } }  public (List<int>[] Edges, Dictionary<int, int> VertexIndexToGroupIndex) GetContractedListTCC() { List<(int u, int v)> bridges = BridgeDetection(0); HashSet<long> set = new HashSet<long>(); List<int>[] CopiedEdges = new List<int>[N]; for (int i = 0; i < N; i++) CopiedEdges[i] = new List<int>(); foreach (var bridge in bridges) { set.Add((long)bridge.u * int.MaxValue + bridge.v); set.Add((long)bridge.v * int.MaxValue + bridge.u); }  for (int from = 0; from < N; from++) { foreach (var e in Edges[from]) { int next = e.Next; long key = (long)from * int.MaxValue + next; if (set.Contains(key)) continue; CopiedEdges[from].Add(next); } }  Queue<int> q = new Queue<int>(); bool[] seen = new bool[N]; int start = 0; List<List<int>> lists = new List<List<int>>(); while (true) { List<int> list = new List<int>(); seen[start] = true; q.Enqueue(start); list.Add(start); while (q.Count > 0) { int cur = q.Dequeue(); foreach (int next in CopiedEdges[cur]) { if (seen[next]) continue; seen[next] = true; list.Add(next); q.Enqueue(next); } }  if (list.Count > 0) lists.Add(list); bool find = false; for (int i = start + 1; i < N; i++) { if (seen[i]) continue; else { start = i; find = true; break; } }  if (!find) break; }  Dictionary<int, int> vertexIndexToGroupIndex = new Dictionary<int, int>(); List<int>[] edges = new List<int>[lists.Count]; for (int group = 0; group < lists.Count; group++) { edges[group] = new List<int>(); foreach (int v in lists[group]) vertexIndexToGroupIndex.Add(v, group); }  HashSet<int>[] sets = new HashSet<int>[N]; for (int from = 0; from < N; from++) sets[from] = Edges[from].Select(_ => _.Next).ToHashSet(); bool IsJoin(int from, int next) => sets[from].Contains(next); foreach (var bridge in bridges) { int u = vertexIndexToGroupIndex[bridge.u]; int v = vertexIndexToGroupIndex[bridge.v]; if (IsJoin(bridge.u, bridge.v)) edges[u].Add(v); if (IsJoin(bridge.v, bridge.u)) edges[v].Add(u); }  (List<int>[] Edges, Dictionary<int, int> VertexIndexToGroupIndex) ret; ret.VertexIndexToGroupIndex = vertexIndexToGroupIndex; ret.Edges = edges; return ret; }  public List<(int u, int v)> BridgeDetection(int start) { List<(int u, int v)> bridges = new List<(int, int)>(); HashSet<int>[] cycle_graph = new HashSet<int>[N]; int[] order = new int[N]; for (int i = 0; i < N; i++) { cycle_graph[i] = new HashSet<int>(); order[i] = -1; }  int cnt = -1; int dfs(int u, int prev) { cnt += 1; int low_pt = order[u] = cnt; foreach (var e in Edges[u]) { int v = e.Next; int v_low_pt = 0; ; if (v == prev) continue; else if (order[v] == -1) { v_low_pt = dfs(v, u); if (v_low_pt > order[u]) { (int u, int v) tp; tp.u = u; tp.v = v; bridges.Add(tp); } else { cycle_graph[u].Add(v); cycle_graph[v].Add(u); }  low_pt = Math.Min(low_pt, v_low_pt); } else { low_pt = Math.Min(low_pt, order[v]); cycle_graph[u].Add(v); cycle_graph[v].Add(u); } }  return low_pt; }  dfs(start, -1); return bridges; }  public long[] Dijkstra(int start) { long[] costs = new long[N]; bool[] seen = new bool[N]; for (int i = 0; i < N; i++) costs[i] = long.MaxValue; PriorityQueue<int, long> pq = new PriorityQueue<int, long>(); pq.Enqueue(start, 0); costs[start] = 0; while (pq.Count > 0) { int cur = pq.Dequeue(); if (seen[cur]) continue; seen[cur] = true; foreach (var e in Edges[cur]) { int next = e.Next; long ncost = costs[cur] + e.Weight; if (costs[next] > ncost) { costs[next] = ncost; pq.Enqueue(next, ncost); } } }  return costs; }  public long[] DijkstraByPotentials(int start) { long[] potentials = GetPotentials(start); for (int i = 0; i < N; i++) { foreach (var e in Edges[i]) { if (e.Weight < potentials[e.Next] - potentials[i]) throw new Exception(); } }  List<Edge>[] edges = new List<Edge>[N]; for (int i = 0; i < N; i++) edges[i] = new List<Edge>(); for (int i = 0; i < N; i++) { edges[i] = new List<Edge>(); foreach (var e in Edges[i]) { edges[i].Add(new Edge(e.Next, e.Weight + potentials[i] - potentials[e.Next])); if (e.Weight + potentials[i] - potentials[e.Next] < 0) { Console.WriteLine("負辺"); throw new Exception(); } } }  long[] costs = new long[N]; bool[] seen = new bool[N]; for (int i = 0; i < N; i++) costs[i] = long.MaxValue; PriorityQueue<int, long> pq = new PriorityQueue<int, long>(); pq.Enqueue(start, 0); costs[start] = 0; while (pq.Count > 0) { int cur = pq.Dequeue(); if (seen[cur]) continue; seen[cur] = true; foreach (var e in edges[cur]) { int next = e.Next; long ncost = costs[cur] + e.Weight; if (costs[next] > ncost) { costs[next] = ncost; pq.Enqueue(next, ncost); } } }  for (int i = 0; i < N; i++) costs[i] += potentials[i] - potentials[start]; return costs; }  public long[] GetPotentials(int start) { long[] potentials = new long[N]; bool[] seen = new bool[N]; for (int i = 0; i < N; i++) potentials[i] = long.MaxValue; PriorityQueue<int, long> pq = new PriorityQueue<int, long>(); pq.Enqueue(start, 0); potentials[start] = 0; while (pq.Count > 0) { int cur = pq.Dequeue(); if (seen[cur]) continue; seen[cur] = true; foreach (var e in Edges[cur]) { long w = e.Weight; int next = e.Next; long np = potentials[cur] + w; if (potentials[next] > np) { potentials[next] = np; pq.Enqueue(next, np); } } }  long min = potentials.Min(); if (min >= 0) return potentials; else return potentials.Select(_ => _ + Math.Abs(min)).ToArray(); }  public long[] Dijkstra(int start, long[] P) { long[] costs = new long[N]; bool[] seen = new bool[N]; for (int i = 0; i < N; i++) costs[i] = long.MaxValue; PriorityQueue<int, long> pq = new PriorityQueue<int, long>(); pq.Enqueue(start, 0); costs[start] = 0; while (pq.Count > 0) { int cur = pq.Dequeue(); if (seen[cur]) continue; seen[cur] = true; foreach (var e in Edges[cur]) { long w = e.Weight / 2; if (e.Weight < 0) w = 0; int next = e.Next; long ncost = costs[cur] + w; if (costs[next] > ncost) { costs[next] = ncost; pq.Enqueue(next, ncost); } } }  for (int i = 0; i < N; i++) costs[i] += P[i] - P[start]; return costs; }  public List<int> GetShortestPath(int start, int goal) { List<int> path = new List<int>(); long[] costs = new long[N]; bool[] seen = new bool[N]; for (int i = 0; i < N; i++) costs[i] = long.MaxValue; int[] froms = new int[N]; PriorityQueue<int, long> pq = new PriorityQueue<int, long>(); pq.Enqueue(start, 0); costs[start] = 0; froms[start] = -1; while (pq.Count > 0) { int cur = pq.Dequeue(); if (seen[cur]) continue; seen[cur] = true; foreach (var e in Edges[cur]) { int next = e.Next; long ncost = costs[cur] + e.Weight; if (costs[next] > ncost) { costs[next] = ncost; froms[next] = cur; pq.Enqueue(next, ncost); } } }  if (costs[goal] == long.MaxValue) return path; int last = goal; while (last != -1) { path.Add(last); last = froms[last]; }  path.Reverse(); return path; }  public long[] Dijkstra(int[] starts) { long[] costs = new long[N]; bool[] seen = new bool[N]; for (int i = 0; i < N; i++) costs[i] = long.MaxValue; PriorityQueue<int, long> pq = new PriorityQueue<int, long>(); foreach (int start in starts) { pq.Enqueue(start, 0); costs[start] = 0; }  while (pq.Count > 0) { int cur = pq.Dequeue(); if (seen[cur]) continue; seen[cur] = true; foreach (var e in Edges[cur]) { int next = e.Next; long ncost = costs[cur] + e.Weight; if (costs[next] > ncost) { costs[next] = ncost; pq.Enqueue(next, ncost); } } }  return costs; }  public bool[] IsWithinDistance(int[] starts, long[] dists) { long[] canMoves = new long[N]; bool[] seen = new bool[N]; for (int i = 0; i < N; i++) canMoves[i] = -1; int len = starts.Length; PriorityQueue<int, long> pq = new PriorityQueue<int, long>(); for (int i = 0; i < len; i++) { pq.Enqueue(starts[i], -dists[i]); canMoves[starts[i]] = dists[i]; }  while (pq.Count > 0) { int cur = pq.Dequeue(); long canMove = canMoves[cur]; if (seen[cur]) continue; seen[cur] = true; foreach (var e in Edges[cur]) { int next = e.Next; long newCanMove = canMove - e.Weight; if (canMoves[next] < newCanMove) { canMoves[next] = newCanMove; pq.Enqueue(next, -newCanMove); } } }  bool[] rets = new bool[N]; for (int i = 0; i < N; i++) { if (canMoves[i] >= 0) rets[i] = true; }  return rets; }  public long[, ] CreateAdjacencyMatrix() { long[, ] mat = new long[N, N]; for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { if (r != c) mat[r, c] = long.MaxValue; } }  for (int a = 0; a < Edges.Length; a++) { foreach (var e in Edges[a]) { int b = e.Next; mat[a, b] = e.Weight; } }  return mat; }  public List<long[, ]> CreateIsomorphismGraphAmatrixes() { long[, ] mat1 = CreateAdjacencyMatrix(); int[] arr = new int[N]; for (int i = 0; i < N; i++) arr[i] = i; List<long[, ]> rets = new List<long[, ]>(); do { long[, ] mat2 = new long[N, N]; for (int a = 0; a < N; a++) { for (int b = 0; b < N; b++) { int a2 = arr[a]; int b2 = arr[b]; if (mat1[a, b] == long.MaxValue) mat2[a2, b2] = long.MaxValue; else mat2[a2, b2] = mat1[a, b]; } }  rets.Add(mat2); } while (AtCoder.StlFunction.NextPermutation(arr)); return rets; }  public static bool IsIsomorphism(Graph g1, Graph g2) { long[, ] adjacencyMatrix1 = g1.CreateAdjacencyMatrix(); long[, ] adjacencyMatrix2 = g2.CreateAdjacencyMatrix(); return IsIsomorphism(adjacencyMatrix1, adjacencyMatrix2); }  public static bool IsIsomorphism(long[, ] adjacencyMatrix1, long[, ] adjacencyMatrix2) { if (adjacencyMatrix1.GetLength(0) != adjacencyMatrix1.GetLength(1)) return false; if (adjacencyMatrix2.GetLength(0) != adjacencyMatrix2.GetLength(1)) return false; if (adjacencyMatrix1.GetLength(0) != adjacencyMatrix2.GetLength(0)) return false; int n = adjacencyMatrix1.GetLength(0); int[] arr = new int[n]; for (int i = 0; i < n; i++) arr[i] = i; do { bool ok = true; for (int a = 0; a < n; a++) { for (int b = 0; b < n; b++) { int a2 = arr[a]; int b2 = arr[b]; if (adjacencyMatrix1[a, b] != adjacencyMatrix2[a2, b2]) { ok = false; break; } } }  if (ok) return true; } while (AtCoder.StlFunction.NextPermutation(arr)); return false; }  public struct FromNextEdge { public FromNextEdge(int from, int next) { From = from; Next = next; }  public int From = 0; public int Next = 0; }  public struct ResultForIsomorphism { public ResultForIsomorphism() { }  public List<FromNextEdge> Add = new List<FromNextEdge>(); public List<FromNextEdge> Remove = new List<FromNextEdge>(); }  public static List<ResultForIsomorphism> GetResultForIsomorphism(Graph g, Graph h) { int N = g.Edges.Length; bool[, ] mat1 = new bool[N, N]; for (int i = 0; i < N; i++) { foreach (var e in g.Edges[i]) { int next = e.Next; mat1[i, next] = true; } }  bool[, ] mat2 = new bool[N, N]; for (int i = 0; i < N; i++) { foreach (var e in h.Edges[i]) { int next = e.Next; mat2[i, next] = true; } }  int[] arr = new int[N]; for (int i = 0; i < N; i++) arr[i] = i; List<ResultForIsomorphism> rets = new List<ResultForIsomorphism>(); do { ResultForIsomorphism ret = new ResultForIsomorphism(); HashSet<string> set2 = new HashSet<string>(); int[] arr2 = new int[N]; for (int i = 0; i < N; i++) arr2[arr[i]] = i; bool[, ] mat3 = new bool[N, N]; for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { if (mat2[r, c]) mat3[arr[r], arr[c]] = true; } }  for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { if (mat1[r, c] && !mat3[r, c]) ret.Add.Add(new FromNextEdge(arr2[r], arr2[c])); if (!mat1[r, c] && mat3[r, c]) ret.Remove.Add(new FromNextEdge(arr2[r], arr2[c])); } }  rets.Add(ret); } while (AtCoder.StlFunction.NextPermutation(arr)); return rets; }  public (List<int>[] Edges, Dictionary<int, int> VertexIndexToGroupIndex) ToDAG() { AtCoder.SccGraph scc = new AtCoder.SccGraph(N); for (int from = 0; from < N; from++) { foreach (var e in Edges[from]) { int next = e.Next; scc.AddEdge(from, next); } }  var groups = scc.Scc(); Dictionary<int, int> vertexIndexToGroupIndex = new Dictionary<int, int>(); List<int>[] edges = new List<int>[groups.Length]; for (int group = 0; group < groups.Length; group++) { edges[group] = new List<int>(); foreach (int v in groups[group]) vertexIndexToGroupIndex.Add(v, group); }  for (int from = 0; from < N; from++) { foreach (var e in Edges[from]) { int next = e.Next; int u = vertexIndexToGroupIndex[from]; int v = vertexIndexToGroupIndex[next]; edges[u].Add(v); } }  (List<int>[] Edges, Dictionary<int, int> VertexIndexToGroupIndex) ret; ret.VertexIndexToGroupIndex = vertexIndexToGroupIndex; ret.Edges = edges; return ret; }  int[] GetInCounts() { int[] counts = new int[N]; for (int a = 0; a < N; a++) { foreach (var e in Edges[a]) { int b = e.Next; counts[b]++; } }  return counts; }  public List<int> TopologicalSort() { int[] counts = GetInCounts(); Queue<int> q = new Queue<int>(); for (int i = 0; i < N; i++) { if (counts[i] == 0) q.Enqueue(i); }  List<int> sorted = new List<int>(); while (q.Count > 0) { int cur = q.Dequeue(); sorted.Add(cur); foreach (var e in Edges[cur]) { int next = e.Next; counts[next]--; if (counts[next] == 0) q.Enqueue(next); } }  if (sorted.Count == N) return sorted; else return new List<int>(); }  public (List<int> Sorted, bool IsUnique) TopologicalSortIsUnique() { List<int> sorted = TopologicalSort(); if (sorted.Count != N) return (Sorted: new List<int>(), IsUnique: false); bool isUnique = true; for (int i = 0; i < N - 1; i++) { int a = sorted[i]; int b = sorted[i + 1]; bool find = false; foreach (var e in Edges[a]) { if (e.Next == b) { find = true; break; } }  if (!find) { isUnique = false; break; } }  return (Sorted: sorted, IsUnique: isUnique); }  public T[] TopologicalSort<T>(List<T> list) { if (list.Count != N) throw new Exception("引数とNが異なる"); List<int> sorted = TopologicalSort(); List<(int, T)> list2 = new List<(int, T)>(); for (int i = 0; i < N; i++) list2.Add((sorted[i], list[i])); list2 = list2.OrderBy(x => x).ToList(); return list2.Select(_ => _.Item2).ToArray(); }  public (List<T> Sorted, bool IsUnique) TopologicalSortIsUnique<T>(List<T> list) { if (list.Count != N) throw new Exception("引数とNが異なる"); (List<int> Sorted, bool IsUnique) ret = TopologicalSortIsUnique(); if (ret.Sorted.Count == 0) return (Sorted: new List<T>(), IsUnique: false); List<(int, T)> list2 = new List<(int, T)>(); for (int i = 0; i < N; i++) list2.Add((ret.Sorted[i], list[i])); list2 = list2.OrderBy(x => x).ToList(); return (Sorted: list2.Select(_ => _.Item2).ToList(), IsUnique: ret.IsUnique); }  public List<(int Goal, long PathCount)> GetPathCounts(long mod) { int[] inCounts = GetInCounts(); List<int> starts = new List<int>(); for (int i = 0; i < N; i++) { if (inCounts[i] == 0) starts.Add(i); }  return GetPathCounts(starts, mod); }  public List<(int Goal, long PathCount)> GetPathCounts(List<int> starts, long mod) { long[] pathCounts = new long[N]; foreach (int start in starts) pathCounts[start] = 1; List<int> sorted = TopologicalSort(); if (sorted.Count != N) return new List<(int Goal, long PathCount)>(); for (int i = 0; i < N; i++) { int from = sorted[i]; foreach (var e in Edges[from]) { int next = e.Next; pathCounts[next] += pathCounts[from]; pathCounts[next] %= mod; } }  var rets = new List<(int Goal, long PathCount)>(); for (int i = 0; i < N; i++) { if (Edges[i].Count == 0) { (int Goal, long PathCount) ret; ret.Goal = i; ret.PathCount = pathCounts[i]; rets.Add(ret); } }  return rets; }  class EdgeForTrail { public EdgeForTrail(int next) { Next = next; }  public int Next = 0; public bool IsUsed = false; public EdgeForTrail Reverse = null; }  List<EdgeForTrail>[] CreateEdgesForTrail() { List<EdgeForTrail>[] edgesForTrail = new List<EdgeForTrail>[N]; for (int i = 0; i < N; i++) edgesForTrail[i] = new List<EdgeForTrail>(); for (int from = 0; from < N; from++) { foreach (var e in Edges[from]) { int next = e.Next; if (from < next) { EdgeForTrail edge1 = new EdgeForTrail(next); edgesForTrail[from].Add(edge1); EdgeForTrail edge2 = new EdgeForTrail(from); edgesForTrail[next].Add(edge2); edge1.Reverse = edge2; edge2.Reverse = edge1; } } }  return edgesForTrail; }  public List<List<int>> GetTrails(int start, int goal) { List<EdgeForTrail>[] edgesForTrails = CreateEdgesForTrail(); List<List<int>> trails = new List<List<int>>(); List<int> trail = new List<int>(); trail.Add(start); dfs(start); return trails; void dfs(int v) { if (v == goal) { if (trail.Count(_ => _ == start) == 1 && trail.Count(_ => _ == goal) == 1) trails.Add(new List<int>(trail)); }  foreach (var edge in edgesForTrails[v]) { if (edge.IsUsed) continue; int next = edge.Next; edge.IsUsed = true; edge.Reverse.IsUsed = true; trail.Add(next); dfs(next); trail.RemoveAt(trail.Count - 1); edge.IsUsed = false; edge.Reverse.IsUsed = false; } } } } }
namespace SourceExpander{public class Expander{[Conditional("EXP")]public static void Expand(string inputFilePath=null,string outputFilePath=null,bool ignoreAnyError=true){}public static string ExpandString(string inputFilePath=null,bool ignoreAnyError=true){return "";}}}
#endregion Expanded by https://github.com/kzrnm/SourceExpander