BubbleTravelNSleep

You are the manager of a company and you want to send some of your employees to a big company meeting, which starts t days from now. The city where the meeting will be held is very far away from your headquarters, so they will have to travel for a couple of days, passing through some other cities and making pauses to sleep and rest during the journey. You have a map that assigns numbers between 1 and n to the cities and shows which of these cities have direct routes between each other. All the employees start from your headquarters (city 1) on the first day. On any given day, each employee can choose either to travel between two connected cities or to stay where he is and rest, and they all have to reach the meeting place (city n) and must not be late for the meeting.

There is just one small problem: your employees hate each other, so you can never allow two or more of them to be in the same city at the same time (except at the start and the end of their journeys, of course). It is allowed for someone to enter a city on the same day when someone else is leaving, however. You kind of hate all of them too, so you don’t want to allow anyone to stay in your headquarters or to return there during the journey.

The meeting is quite important, so you would like to send as many people there as possible, and now you want to calculate exactly how many is that.

Explanation: On the first day, the first person can go to city 2 and the second can go to city 3, and they will both reach city 4 on the second day.