Cow and Fields

Bessie is out grazing on the farm, which consists of n fields connected by m bidirectional roads. She is currently at field 1, and will return to her home at field n at the end of the day.

The Cowfederation of Barns has ordered Farmer John to install one extra bidirectional road. The farm has k special fields and he has decided to install the road between two different special fields. He may add the road between two special fields that already had a road directly connecting them.

After the road is added, Bessie will return home on the shortest path from field 1 to field n. Since Bessie needs more exercise, Farmer John must maximize the length of this shortest path. Help him!Input

The first line contains integers n, m, and k (2n2105, n1m2105, 2kn)  — the number of fields on the farm, the number of roads, and the number of special fields.

The second line contains k integers a1,a2,,ak (1ain)  — the special fields. All ai are distinct.

The i-th of the following m lines contains integers xi and yi (1xi,yin, xiyi), representing a bidirectional road between fields xi and yi.

It is guaranteed that one can reach any field from every other field. It is also guaranteed that for any pair of fields there is at most one road connecting them.Output

Output one integer, the maximum possible length of the shortest path from field 1 to n after Farmer John installs one road optimally.Examplesinput

5 5 3
1 3 5
1 2
2 3
3 4
3 5
2 4

output

3

input

5 4 2
2 4
1 2
2 3
3 4
4 5

output

3

Note

The graph for the first example is shown below. The special fields are denoted by red. It is optimal for Farmer John to add a road between fields 3 and 5, and the resulting shortest path from 1 to 5 is length 3.

The graph for the second example is shown below. Farmer John must add a road between fields 2 and 4, and the resulting shortest path from 1 to 5 is length 3.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <bits/stdc++.h>
 
using namespace std;
 
template <typename A, typename B>
string to_string(pair<A, B> p);
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
 
string to_string(const string& s) {
return '"' + s + '"';
}
 
string to_string(const char* s) {
return to_string((string) s);
}
 
string to_string(bool b) {
return (b ? "true" : "false");
}
 
string to_string(vector<bool> v) {
bool first = true;
string res = "{";
for (int i = 0; i < static_cast<int>(v.size()); i++) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(v[i]);
}
res += "}";
return res;
}
 
template <size_t N>
string to_string(bitset<N> v) {
string res = "";
for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
}
return res;
}
 
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m, k;
  cin >> n >> m >> k;
vector<int> spec(n, 0);
for (int i = 0; i < k; i++) {
    int foo;
    cin >> foo;
--foo;
spec[foo] = 1;
}
vector<vector<int>> g(n);
for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
--x; --y;
g[x].push_back(y);
g[y].push_back(x);
}
vector<int> a(n, -1);
vector<int> b(n, -1);
for (int rot = 0; rot < 2; rot++) {
    vector<int> que(1, (rot == 0 ? 0 : n - 1));
vector<int>& dist = (rot == 0 ? a : b);
dist[que[0]] = 0;
for (int b = 0; b < (int) que.size(); b++) {
      for (int j : g[que[b]]) {
        if (dist[j] == -1) {
          que.push_back(j);
          dist[j] = dist[que[b]] + 1;
        }
      }
    }
  }
  vector<pair<int, int>> v;
for (int i = 0; i < n; i++) {
    if (spec[i]) {
      v.emplace_back(a[i], b[i]);
    }
  }
  int sz = (int) v.size();
  sort(v.begin(), v.end(), [&](const pair<int, int>& x, const pair<int, int>& y) {
return x.first - x.second < y.first - y.second;
  });
  int ans = 0;
  int mx = v[0].first;
  for (int i = 1; i < sz; i++) {
    ans = max(ans, mx + 1 + v[i].second);
    mx = max(mx, v[i].first);
  }
  ans = min(ans, a[n - 1]);
  cout << ans << '\n';
  return 0;
}