What is the Problem?
Every morning, Lisa drives a public bus from one terminal to the other. Through months of careful observation, she has noticed that the order in which buses complete the route isn't necessarily the order in which they started. It is possible for the first bus to arrive at the first stop to not be the first bus to leave the last stop due to delays along the route. To leave work as early as possible, Lisa would like to figure out which bus will finish teh route first on a given morning.
The route has N bus stops (labelled 1 to N) and M daily passengers. Each passenger gets on a bus at some stop and gets off at a later stop. Each morning, the buses (labelled 1, 2, 3, ...) start at the first stop in 10-minute intervals, i.e., the k+1st bus starts 10 minutes after the kth bus.
A bus takes one minute to travel from one stop to the next. Each bus can carry 40 people. Passengers at a bus stop board the buses in the order that they arrive at the stop. A bus will only stop at a bus stop if it is not full and there is a opassenger waiting at the stop, or if someone ont eh bus wants to get off at the stop. If a bus stops, it first lets off any passengers taht want to get off the bus, then pics up as many passengers taht is can. Stopping delays a bus by one minute, regardless of hwo many people it picks up or drops off. If multiple buses arrive at a stop at the same time, tehy would stop increasing order of their indices (i.e., the bus with teh lowest index stops first).
Can you help Lisa by figuring out which bus she should drive to complete the route first?
Input Specifications
DATA41.txt (DATA42.txt for the second try) will contain 10 datasets.
Each dataset begins with two integers N, M (1≤ N, M ≤ 500,000). The next M lines each contain two integers, S, F (1≤ S < F ≤ N), whjich represent a passenger who wants to travel between stop S and stop F. If multiple people start at the same stop, buses pick them up in the order that they are listed.
For the first 4 datasets, N, M ≤ 1,000.
Output Specifications
For each dataset, output "Bus #X", where X is the index of the bus taht will be the first to reach the last stop. If two buses tie for first, output the one with the lower index.
Sample Input (Two Datasets Shown)
5 3
1 2
2 3
4 5
13 6
1 7
2 8
3 9
4 10
5 11
6 12
Sample Output
Bus #1
Bus #2