Traveling Trio
Description
In the country of Byterland, cities are laid out along the shore of a beautiful river that flows from north to south. The northernmost city is labeled number 1, the city directly to its south is labeled number 2, etc. During the summer, ships are only allowed to travel south, or stay where they are, due to the huge number of tourists. There is always a route from each city i to city i + 1. Additional routes between cities may also exist, including possibly routes between a city and itself.
Three people are planning to take journeys down the river, and they would like to coordinate their travel plans in order to minimize their total cost. Each person has their own individual starting and ending cities. The cost of traveling on any single ship route is always 1 dollar. If two or three people take the same route together as a group, the total ticket price is 1 dollar for the whole group. Please calculate the minimum total cost paid by the trio of travelers.
Input
On the first line of the input you will be given an integer N (1 ≤ N ≤ 1000) representing the number of cities, and an integer M (M ≤ 10000) representing the number of routes to be given below (excluding the mandatory routes from each city i to city i + 1).
The following M pairs of integers each contain a piece of information for a single route, in the form of “A B” where A indicates the starting city of this route and B shows the ending city. (1 ≤ A ≤ B ≤ N) These pairs will be separated by spaces or empty lines.
The next line contains three integers S1, S2, S3 – the starting cities of the three travelers. Similarly, the last line contains three integers E1, E2, E3 – the ending cities of the three travelers. (1 ≤ S1, S2, S3, E1, E2, E3 ≤ N, Si ≤ Ei, i = 1, 2, 3).
This is a multiple test cases problem. Test cases are followed by blank lines. Please process to the end of the file.
Output
For each test case, output a single line with an integer representing the minimum total cost paid by the trio of travellers.
3 1
1 3
1 1 2
2 3 3
3 5
1 3 1 2 1 3 1 3
1 1
1 1 2
2 3 3
1 0
1 1 1
1 1 1
6 4
1 4 1 3 2 2 3 4
2 5 2
6 6 2
12 16
3 8 1 1 5 8 1 4 4 7 9 12 2 7 5 5 2 8 2 10
1 3 7 11 7 12 1 8 2 6 4 11
1 3 5
4 7 5
2
2
0
4
3Hint
Explanations of the sample test cases:
For the first case:
- 1st person: 1→2
- 2nd person: 1→2→3
- 3rd person: 2→3
The first and second person can share the ship going from city 1 to city 2. The second and third person can then share the ship going from city 2 to city 3. Only two ship routes are used, so the total cost is two dollars.
For the second case:
Exactly the same as the first test case. Duplicate routes and self-cycles can sometimes exist. Please remember that the 1→2 route is also a duplicate since the mandatory i→(i + 1) routes are not in our list.
Source
POJ Monthly--2006.12.31, Zhu, Zeyuan
</p>