| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 2048 MB | 40 | 21 | 19 | 54.286% |
FC Porto and SL Benfica are the two largest football teams in Portugal. Naturally, when the two play each other, a lot of people travel from all over the country to watch the game. This includes the Benfica supporters’ club, which is going to travel from Lisbon to Porto to watch the upcoming game. To avoid tensions between them and the Porto supporters’ club, the national police want to delay their arrival to Porto as much as they can.
The road network in Portugal can be modelled as a simple, undirected, unweighted, connected graph with $n$ vertices and $m$ edges, where vertices represent towns and edges represent roads. Vertex 1ドル$ corresponds to Lisbon, i.e., the starting vertex of the supporters’ club, and vertex $n$ is Porto, i.e., the destination vertex of the supporters’ club. The supporters’ club wants to minimize the number of roads they take to reach Porto.
The police are following the supporters’ club carefully, and so they always know where they are. To delay their arrival, at any point the police can pick exactly one road and block it, as long as the supporters’ club isn’t currently traversing it. They can do this exactly once, and once they do that, the road is blocked forever. Once the police block a road, the supporters’ club immediately learns that that road is blocked, and they can change their route however they prefer. Furthermore, the supporters’ club knows that the police are planning on blocking some road and can plan their route accordingly.
Assuming that both the supporters’ club and the police always make optimal choices, determine the minimum number of roads the supporters’ club needs to traverse to go from Lisbon to Porto. If the police can block the supporters’ club from ever reaching Porto, then output -1.
The first line contains two integers $n$ and $m$ (2ドル ≤ n ≤ 200,円 000,ドル $n−1 ≤ m ≤ \min\{n(n-1)/2, 200,円 000\}$) — the number of towns and the number of roads in the road network of Portugal.
Each of the next $m$ lines contains two integers $s_i$ and $t_i$ (1ドル ≤ s_i , t_i ≤ n$) — the two towns connected by the $i$-th road.
It is guaranteed that the road network is connected, each road connects two distinct towns, and that there are no repeated roads.
Print the minimum number of roads the supporters’ club needs to traverse to travel from Lisbon to Porto.
5 5 1 2 1 3 2 5 3 4 4 5
5
The road network is represented by the following picture:
Note that the optimal strategy for the police is to wait until the supporters’ club is on a vertex adjacent to the destination (i.e., vertex 5ドル$) and then block the edge that connects that vertex to the destination. The optimal strategy for the supporters’ club is to follow the upper path (by going from 1ドル$ to 2ドル$) and then after seeing the edge between 2ドル$ and 5ドル$ get blocked, they will go around by following 2ドル$ back to 1ドル$ and then following the lower path (1ドル$ to 3ドル$ to 4ドル$ to 5ドル$). The number of traversed roads in this case is 5ドル$.
11 12 1 2 2 3 3 4 4 5 5 11 3 6 6 7 7 11 1 8 8 9 9 10 10 11
9
The road network is represented by the following picture:
There are multiple strategies here, but one can verify that the optimal one for both the police and supporters’ club is to follow the upper path (1ドル → 2 → 3 → 4 → 5$), then the police block the edge 5ドル$ to 11ドル,ドル and so the supporters’ club go around by following 5ドル → 4 → 3 → 6 → 7 → 11$. The total number of traversed roads of this strategy is 9ドル$.
8 10 1 2 2 3 3 4 3 8 4 8 1 5 5 6 6 7 6 8 7 8
5
The road network is represented by the following picture:
The optimal strategy for the police is to block edge 2ドル$ to 3ドル$ if the supporters’ club reaches vertex 2ドル,ドル or block edge 5ドル$ to 6ドル$ if the supporters’ club reaches vertex 5ドル$. The optimal path in this case is 1ドル → 2 → 1 → 5 → 6 → 8$. The total number of traversed roads in this case is 5ドル$.