WC '17 Contest 4 S2 - Strange Travels

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.8s
Memory limit: 64M

Problem type
Woburn Challenge 2017-18 Round 4 - Senior Division

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 \le N \le 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 \le M \le
200\,000) one-way portals, with the i-th of them allowing for instantaneous travel from sanctum A_{i} to B_{i} (1 \le A_{i},
B_{i} \le N, A_{i} \neq B_{i}). No two portals connect the same pair of sanctums in the same direction.

There are K (1 \le K \le N - 1) artifacts which Strange requires, with the i-th of them being held in sanctum S_{i} (2 \le S_{i} \le
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 \rightarrow S_{1} \rightarrow 1 \rightarrow S_{2} \rightarrow 1 \rightarrow \ldots \rightarrow 1 \rightarrow S_{K} \rightarrow 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.


In test cases worth 6/20 of the points, N \le 100 and M \le 2\,000.
In test cases worth another 6/20 of the points, N \le 2\,000 and M \le

Input Specification

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 \ldots M.
The next line consists of K integers, S_{1\ldots K}.

Output Specification

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
4 2

Sample Output 1


Sample Input 2

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

Sample Output 2


Sample Explanations

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

1 \rightarrow 3 \rightarrow 4 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 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.


There are no comments at the moment.