Informatica Online Judge

  Avoid #1 [2238 / 08BE]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 3   Total Tried : 4


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[35th 임유진]
Writer ID : [gs17100]

Background

유진이는 학교에서 다양한 일을 겪은 후, 마주치지 않고 싶은 사람들이 생겼다.

처음에는 그들을 무시하려고 했으나, 그 사람들은 지나가다가 만나면 유진이를 붙잡고 이상한 것들에 대해 따지고는 했다.

그래서 유진이는 그 사람들과 같은 공간에 있는 시간을 최소화하려고 한다.

경곽은 N개의 정점과 M개의 양방향 간선으로 이루어진 그래프이다.

사람들은 각 정점에 1의 시간을 서있은 후 간선을 통해 연결된 정점으로 이동한다.(이동하지 않을 수도 있다)

유진이는 현재 1번 정점에 서있고, N번 정점으로 가야 한다.

N번 정점에 도착한 후에는 피하고자 하는 사람을 마주칠 걱정을 하지 않아도 된다.

유진이가 피하고 싶은 사람들은 총 X명이고, 현재 a_i 위치에 있다. (1<=i<=X)

유진이는 그 사람들이 어디로 이동할 지 알 수 없다.

그렇기 때문에 유진이는 특정 시점에, 자신이 피하고자 하는 사람이 있을 가능성이 있는 공간에 최대한 적게 가고 싶어한다.

어떻게 하면 유진이가 피하고자 하는 사람과 마주칠 가능성이 있는 시간을 최소화할 수 있을지 구해주자!

Input

첫 줄에는 정점의 개수 N과 간선의 개수 M, 그리고 피하고 싶은 사람의 수 X가 공백으로 구분되어 주어진다. (2<=N<=100000, 0<=M<=1000000, 0<=X<=1000000)

둘째 줄부터 M개의 줄에는 간선으로 연결된 두 정점 p, q가 주어진다. (1<=p, q<=N, p!=q)

그 다음 줄에는 유진이가 피하고자 하는 사람의 현재 위치 a_i가 공백으로 구분되어 주어진다. (1<=i<=X)

서브태스크
#1: N<=1000, M<=100000

Output

유진이가 최적의 경로로 N번 경로까지 갈 때, 유진이가 피하고자 하는 사람과 마주칠 가능성이 있는 시간을 출력한다.

N번 정점에 도달할 수 없다면 "Flee" 출력한다.
("Flee"란, 학교에서 재빨리 도망친다는 뜻이다.)

IO Example

입력1
5 5 1
1 2
2 3
3 4
4 1
3 5
2

출력1
2

입력2
2 1 2
1 2
1 2

출력2
2

1번 예제 설명
t=0: 유진이는 1에 있고, 1번 사람은 2에 있다.
t=1: 유진이는 4에 있고, 1번 사람은 1, 2 또는 3에 있다.
t=2: 유진이는 3에 있고, 1번 사람은 1, 2, 3, 4, 5 중 하나에 있다.
t=3: 유진이는 5에 있고, 1번 사람은 1, 2, 3, 4, 5 중 하나에 있다.
t=2와 t=3에서 피하고자 하는 사람을 마주칠 수 있기 때문에 답은 2이다.

2번 예제 설명
t=0: 유진이는 1, 1번 사람은 1, 2번 사람은 2에 있다.
t=1: 유진이는 2, 1번 사람은 1 또는 2, 2번 사람은 1 또는 2에 있다.
t=0또는 t=1에서 피하고자 하는 사람을 마주칠 수 있기 때문에 답은 2이다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]