## DMOPC '18 Contest 2 P3 - Thanksgiving Feast

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Java 2.5s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Mimi is attending a Thanksgiving feast! She lives in a town with buildings numbered from to and unweighted bidirectional roads connecting them. The road connects buildings and . Mimi is a good guest, so she wants to bring a gift for the host. However, Mimi is also a procrastinator! The Thanksgiving feast is soon and she hasn't bought a gift yet. There are buildings which sell gifts. Mimi is currently at building and the feast is at building . She needs to visit at least one of the buildings and go to the feast. Help her find the length of the shortest way to do so!

It is guaranteed that there exists a way. Mimi is allowed to pass through before buying a gift.

#### Input Specification

The first line of input will contain a five space-separated integers , , , , .
The next line will contain space-separated integers representing the buildings which sell gifts.
The next lines each contain two space-separated integers, and .

#### Output Specification

Output a single integer, the shortest distance.

#### Sample Input 1

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

#### Sample Output 1

3

#### Explanation for Sample 1

Mimi starts at building 1. She passes by , to head to . She then returns to , giving a total length of .

#### Sample Input 2

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

#### Sample Output 2

4