using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("4 3");
WillReturn.Add("1 4");
WillReturn.Add("2 4");
WillReturn.Add("3 4");
WillReturn.Add("3");
WillReturn.Add("1 2 3");
//5
}
else if (InputPattern == "Input2") {
WillReturn.Add("4 3");
WillReturn.Add("1 4");
WillReturn.Add("2 4");
WillReturn.Add("1 2");
WillReturn.Add("3");
WillReturn.Add("1 2 3");
//-1
}
else if (InputPattern == "Input3") {
WillReturn.Add("10 10");
WillReturn.Add("3 9");
WillReturn.Add("3 8");
WillReturn.Add("8 10");
WillReturn.Add("2 10");
WillReturn.Add("5 8");
WillReturn.Add("6 8");
WillReturn.Add("5 7");
WillReturn.Add("6 7");
WillReturn.Add("1 6");
WillReturn.Add("2 4");
WillReturn.Add("4");
WillReturn.Add("1 2 7 9");
//11
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static Dictionary<int, List<int>> mToNodeListDict = new Dictionary<int, List<int>>();
static int[] mCArr;
// Cのペアの最短距離
static int?[,] mMinKyoriArr;
static void Main()
{
List<string> InputList = GetInputList();
int[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();
SplitAct(InputList[0]);
int M = wkArr[1];
foreach (string EachStr in InputList.Skip(1).Take(M)) {
SplitAct(EachStr);
int FromNode = wkArr[0];
int ToNode = wkArr[1];
if (mToNodeListDict.ContainsKey(FromNode) == false) {
mToNodeListDict[FromNode] = new List<int>();
}
mToNodeListDict[FromNode].Add(ToNode);
if (mToNodeListDict.ContainsKey(ToNode) == false) {
mToNodeListDict[ToNode] = new List<int>();
}
mToNodeListDict[ToNode].Add(FromNode);
}
mCArr = InputList[M + 2].Split(' ').Select(pX => int.Parse(pX)).ToArray();
mMinKyoriArr = new int?[mCArr.Length, mCArr.Length];
int Result = Solve();
Console.WriteLine(Result);
}
static int Solve()
{
for (int I = 0; I <= mCArr.GetUpperBound(0); I++) {
mMinKyoriArr[I, I] = 0;
}
foreach (int EachA in mCArr) {
ExecBFS(EachA);
}
// 到達不能なペアがあったら、解なし
for (int I = 0; I <= mMinKyoriArr.GetUpperBound(0); I++) {
for (int J = I + 1; J <= mMinKyoriArr.GetUpperBound(1); J++) {
if (mMinKyoriArr[I, J].HasValue == false) {
return -1;
}
}
}
return ExecDP();
}
struct JyoutaiDef
{
internal int CurrNode;
internal int Cost;
}
static void ExecBFS(int pStaNode)
{
var Que = new Queue<JyoutaiDef>();
JyoutaiDef WillEnqueue;
WillEnqueue.CurrNode = pStaNode;
WillEnqueue.Cost = 0;
Que.Enqueue(WillEnqueue);
var VisitedSet = new HashSet<int>();
VisitedSet.Add(pStaNode);
var NeedVisitSet = new HashSet<int>();
NeedVisitSet.UnionWith(mCArr.Where(pX => pX > pStaNode));
while (Que.Count > 0) {
JyoutaiDef Dequeued = Que.Dequeue();
if (NeedVisitSet.Contains(Dequeued.CurrNode)) {
int CInd1 = GetCInd(pStaNode);
int CInd2 = GetCInd(Dequeued.CurrNode);
mMinKyoriArr[CInd1, CInd2] = Dequeued.Cost;
mMinKyoriArr[CInd2, CInd1] = Dequeued.Cost;
NeedVisitSet.Remove(Dequeued.CurrNode);
}
// クリア判定
if (NeedVisitSet.Count == 0) {
break;
}
if (mToNodeListDict.ContainsKey(Dequeued.CurrNode)) {
foreach (int EachToNode in mToNodeListDict[Dequeued.CurrNode]) {
if (VisitedSet.Add(EachToNode)) {
WillEnqueue.CurrNode = EachToNode;
WillEnqueue.Cost = Dequeued.Cost + 1;
Que.Enqueue(WillEnqueue);
}
}
}
}
}
// CArrの値に対応する添字を返す
static int GetCInd(int pCVal)
{
return Array.BinarySearch(mCArr, pCVal);
}
// TSP問題として、BitDPで解く
static int ExecDP()
{
int UB = mCArr.GetUpperBound(0);
int AllBitOn = (1 << mCArr.Length) - 1;
// 最小コスト[現在位置,訪問済なmCArrの添字] なDP表
int?[,] PrevDP = new int?[UB + 1, AllBitOn + 1];
for (int I = 0; I <= UB; I++) {
PrevDP[I, 1 << I] = 1; // 辺の数でなく、ノード数なので、初期値は1
}
for (int I = 1; I <= mCArr.Length - 1; I++) {
int?[,] CurrDP = new int?[UB + 1, AllBitOn + 1];
for (int J = 0; J <= UB; J++) {
for (int K = 0; K <= AllBitOn; K++) {
if (PrevDP[J, K].HasValue == false) continue;
for (int L = 0; L <= UB; L++) {
int CurrBit = 1 << L;
if ((K & CurrBit) > 0) continue;
int NewJ = L;
int NewK = K | CurrBit;
int AddCost = mMinKyoriArr[J, L].Value;
int NewVal = PrevDP[J, K].Value + AddCost;
if (CurrDP[NewJ, NewK].HasValue) {
if (CurrDP[NewJ, NewK].Value <= NewVal) {
continue;
}
}
CurrDP[NewJ, NewK] = NewVal;
}
}
}
PrevDP = CurrDP;
}
return PrevDP.Cast<int?>().Min().Value;
}
}