Woburn Challenge 2017-18 Round 4 - Senior Division

Problem 2: Strange Travels

Desperate to find more allies to join in the fight against Thanos, the Avengers have requested assistance from Doctor Strange, a powerful magician. Strange is willing to help, but he'll need some assistance of his own first. To fully apply his powers to the fight, he'll need to gather together a set of artifacts from hidden sanctums around the world!

There are N (2 ≤ N ≤ 100,000) sanctums, numbered from 1 to N, spread out all across the Earth. It would take far too long to travel amongst them by conventional means, but Doctor Strange has access to a convenient alternative – magical portals. There are M (0 ≤ M ≤ 200,000) one-way portals, with the i-th of them allowing for instantaneous travel from sanctum A_i to B_i (1 ≤ A_i, B_i ≤ N, A_i ≠ B_i). No two portals connect the same pair of sanctums in the same direction.

There are K (1 ≤ K ≤ N − 1) artifacts which Strange requires, with the i-th of them being held in sanctum S_i (2 ≤ S_i ≤ N). No artifact is in sanctum 1, and no two artifacts are located in the same sanctum.

Doctor Strange is initially located in sanctum 1, also known as the Sanctum Sanctorum. He'll need to recover all K artifacts back to the Sanctum Sanctorum, one by one. In particular, for each artifact i in order, he'll need to warp through a sequence of 1 or more portals to reach sanctum S_i, collect the artifact, and then warp through a sequence of 1 or more portals to return to sanctum 1 before heading back out for the next one. Note that he may not carry multiple artifacts at a time, and must collect the K artifacts in order. Overall, he'll be required to visit the following sequence of sanctums:

1 → S₁ → 1 → S₂ → 1 → … → 1 → S_K → 1

Determine the minimum number of portal warps which Doctor Strange will need to perform to achieve his goal. Unfortunately, it may instead turn out to be impossible to visit the entire required sequence of sanctums, in which case you should output −1 instead.

Subtasks

In test cases worth 6/20 of the points, N ≤ 100 and M ≤ 2000.
In test cases worth another 6/20 of the points, N ≤ 2000 and M ≤ 2000.

Input Format

The first line of input consists of two space-separated integers, N and M.
M lines follow, the i-th of which consists of two space-separated integers, A_i and B_i, for i = 1..M.
The next line consists of K integers, S_1..K.

Output Format

Output a single integer, either the minimum number of warps required to recover all of the artifacts, or −1 if not all of them can be recovered.

Sample Input 1

4 6
1 2
2 3
3 1
1 3
4 3
3 4
2
4 2

Sample Output 1

7

Sample Input 2

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

Sample Output 2

-1

Sample Explanations

In the first case, Doctor Strange can warp through the following sequence of sanctums:

1 → 3 → 4 → 3 → 1 → 2 → 3 → 1

In the second case, Doctor Strange would be able to recover the first artifact and then reach the second one, but he would then be unable to return to sanctum 1 with it.

All Submissions
Best Solutions

Point Value: 12 (partial)
Time Limit: 4.00s
Memory Limit: 64M
Added: Apr 20, 2018
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)