In the city there are N districts (numbered from 0 to N-1) connected with M streets. The connections are described by two arrays, A and B, both of length M. A pair (A[K], B[K]) marks a street between districts A[K] and B[K] (for K from 0 to M-1).

There are also L hospitals whose locations are described by an array H. The J-th hospital is placed in district H[J] (for J from 0 to L-1).

If an ambulance is needed in a district, one is sent from the hospital from which it will arrive in the shortest time. The ambulance arrives by the shortest possible route; passing one street takes it exactly 1 minute.

Potentially, there might be a patient in need in any district of the city. What is the longest time required to reach any possible patient with an ambulance?

Function

Write a function:

int solution(int N, vector<int> &A, vector<int> &B, vector<int> &H);

that, given an integer N, arrays A and B describing streets in the city, and an array H giving the locations of hospitals, returns an integer — the longest driving time (in minutes) between a district and its closest hospital.

If some district cannot be reached with an ambulance, the function should return -1.

---

Examples

Example 1

Given:

N = 6
A = [0, 1, 1, 3, 0]
B = [1, 2, 3, 4, 5]
H = [2, 4]

Your function should return 3.

District 5 has the longest waiting time.

Graph

          2 🏥
          |
          1
         / \
        0   3
        |    |
        5    4 🏥

Edges:

0 — 1
1 — 2
1 — 3
3 — 4
0 — 5

Hospitals: 2, 4

Distances to the nearest hospital:

District 0 → 2
District 1 → 1
District 2 → 0
District 3 → 1
District 4 → 0
District 5 → 3

Therefore:

Answer = 3

---

Example 2

Given:

N = 6
A = [0, 1, 1, 3, 0, 4]
B = [1, 2, 3, 4, 5, 5]
H = [2, 4]

Your function should return 2.

The district with the longest ambulance arrival time is district 0. Every other district can be reached by an ambulance in at most 1 minute.

Graph

          2 🏥
          |
          1
         / \
        0   3
        |    |
        5 —  4 🏥

More precisely, the edges are:

0 — 1
1 — 2
1 — 3
3 — 4
0 — 5
4 — 5

Hospitals: 2, 4

Distances to the nearest hospital:

District 0 → 2
District 1 → 1
District 2 → 0
District 3 → 1
District 4 → 0
District 5 → 1

Therefore:

Answer = 2

---

Example 3

Given:

N = 6
A = [0, 1, 1, 3]
B = [1, 2, 3, 4]
H = [2, 4]

Your function should return -1.

District 5 is not connected with any district with a hospital.

Graph

          2 🏥
          |
          1
         / \
        0   3
             |
             4 🏥

        5
     (isolated)

Edges:

0 — 1
1 — 2
1 — 3
3 — 4

District 5 has no connection to any hospital.

Therefore:

Answer = -1

---

Example 4

Given:

N = 3
A = [1]
B = [2]
H = [0, 1, 2]

Your function should return 0.

There is a hospital in every district.

Graph

     0 🏥

     1 🏥 — 2 🏥

Since every district already contains a hospital:

District 0 → 0
District 1 → 0
District 2 → 0

Therefore:

Answer = 0

---

Constraints

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..100,000];
• M is an integer within the range [0..100,000];
• L is an integer within the range [1..N];
• the elements of H are all distinct;
• each element of arrays A, B and H is an integer within the range [0..N-1];
• every street goes between two different districts;
• there are no multiple streets between two districts.