2305. Pirates’ Path

输入格式

Input consists of $b+1$ lines where $b$ is the number of bridges on the island. The first line contains $4$ numbers separated by a single space:

$nbse$

$n$ is the number of areas on the island, $b$ is the number of bridges, $s$ (where $0\le s<n$) is the area where Captain Jack is being held and $e$ (where $0\le e<n$) is the area where the Black Pearl is located. Each of the next $b$ lines describes a bridge. The line will contain $3$ numbers separated by a single space:

$abc$

$a$ and $b$, $0\le a,b<n$ are the areas connected by the bridge described by the line and $c$ is a bit, either $0$ or $1$, indicating whether the bridge is being guarded by a man or not. If it is being guarded, only one man will be a guard.

$0\le n\le 100000,0\le b\le 1000000$

输出格式

Note that there may not be a path from the area where Captain Jack is being kept to the area of the Black Pearl. If this is the case, output should be a single line containing the following (quotes for clarity):

It’s over with Captain Jack. At least till Pirates of the Caribbean 3.

In case there is a path to the Black Pearl, output should be a single line containing (quotes for clarity):

x native(s) on the easiest way for Captain Jack.

where $x$ should be replaced by the least number of natives guarding bridges on a path from the starting area to the area of the Black Pearl.

6 5 1 5
0 1 0
0 2 0
1 2 0
1 3 1
3 4 0

It’s over with Captain Jack. At least till Pirates of the Caribbean 3.

7 11 0 6
0 1 0
0 2 1
1 2 0
1 3 1
2 4 0
1 5 1
3 5 0
3 4 1
3 6 0
4 5 1
5 6 1

1 native(s) on the easiest way for Captain Jack.