logo
    • Build Project
    • Challenges
    • Interviews
    • More
Sign in

Description

Medium

The Memory Palace Corridors

Loading content...

Input Format

Loading content...

Output Format

Loading content...

Examples

Example 1

Input
5 6 1 1 2 1 3 2 4 3 4 4 5 2 5 3
Output
3
ExplanationPath 1->2->4->5 or 1->2->5 both avoid room 3. Shortest is 1->2->5 with 2 corridors. Wait, 1->2->5 is 2 edges.

Example 2

Input
3 2 1 1 2 2 3 2
Output
-1
ExplanationRoom 2 is a distraction and its the only path from 1 to 3.

Constraints

•

2 ≤ n ≤ 1000

•

1 ≤ m ≤ 10000

•

0 ≤ d < n-1

•

Rooms 1 and n are never distractions

Code

Python
​
Login
Error

Case 1

Case 2

Input
5 6 1 1 2 1 3 2 4 3 4 4 5 2 5 3
Output
No output
Expected
2

A detective uses a "memory palace" technique where memories are stored in rooms connected by corridors. The palace is represented as an undirected graph with n rooms (numbered 1 to n) and m corridors.

The detective starts in room 1 and needs to reach room n. However, some rooms contain distractions that must be avoided.

Determine the minimum number of corridors the detective must traverse to reach room n from room 1 while avoiding all distraction rooms. If it's impossible, return -1.

Room 1 and room n are guaranteed to NOT be distraction rooms.

The first line contains three integers n, m, and d (rooms, corridors, distractions). The next m lines each contain two integers u and v representing a corridor between rooms u and v. The last line contains d space-separated integers representing the distraction room numbers.

Print the minimum number of corridors to traverse, or -1 if impossible.