CF721C Journey

Recently Irina arrived to one of the most famous cities of Berland — the Berlatov city. There are $ n $ showplaces in the city, numbered from $ 1 $ to $ n $ , and some of them are connected by one-directional roads. The roads in Berlatov are designed in a way such that there are no cyclic routes between showplaces. Initially Irina stands at the showplace $ 1 $ , and the endpoint of her journey is the showplace $ n $ . Naturally, Irina wants to visit as much showplaces as she can during her journey. However, Irina's stay in Berlatov is limited and she can't be there for more than $ T $ time units. Help Irina determine how many showplaces she may visit during her journey from showplace $ 1 $ to showplace $ n $ within a time not exceeding $ T $ . It is guaranteed that there is at least one route from showplace $ 1 $ to showplace $ n $ such that Irina will spend no more than $ T $ time units passing it.

N/A

N/A