Problem B
Brýr
Languages
en
is
ja

As everyone knows from last year, Eva and Stefán live in Vestmannaeyjar. You helped Eva find the best travel plan to tour the entire country with Stefán in the least amount of time. Now Eva wants to visit Egilsstaðir, but travelling around the country lead to them finding out that Stefán HATES single-lane bridges. Thus Eva looks to you once more to keep Stefán in a good mood.
Can you help Eva find the way from Vestmannaeyjar to Egilsstaðir using the least amount of single-lane bridges?
Input
On the first line there are two integers,
Output
One line containing the minimal number of single-lane bridges Stefán and Eva have to cross to get to their destination.
Scoring
Group |
Points |
Constraints |
1 |
20 |
|
2 |
20 |
|
3 |
20 |
|
4 |
20 |
All roads contain a single-lane bridge ( |
5 |
20 |
No further constraints |
Sample Input 1 | Sample Output 1 |
---|---|
3 3 3 1 1 1 2 1 2 3 1 |
1 |
Sample Input 2 | Sample Output 2 |
---|---|
6 6 5 6 1 5 4 1 2 1 1 2 3 1 4 3 1 1 4 1 |
3 |
Sample Input 3 | Sample Output 3 |
---|---|
10 13 7 3 0 7 10 1 8 2 0 10 2 1 4 6 0 4 1 0 9 5 1 6 9 0 7 6 1 3 10 0 4 5 0 5 7 1 4 8 0 |
1 |