Today is Valentine’s day, and Pisces is going to date with the beautiful princess in the neighboring kingdom. There are \(n\) cities numbered from \(1\) to \(n\) on the mainland, with Pisces in city \(1\) and the princess in city \(n\). There are \(m\) unidirectional roads among these \(n\) cities. Usually, it takes Pisces \(1\) unit of time to travel from one city to another, but due to the probable existence of thorns, rivers or even robbers, some of the roads will take \(2\) units of time to travel. In other words, the cost of traveling from one city to another is either \(1\) unit or \(2\) units of time. Pisces wants to know the minimum time that he can meet the princess.