Alice and Bob broke up finally. There are n cities, there is either a road or a railway between every two cities. There is a railway between two cities if and only if there are no road between these cities. Each road and railway will cost 1 time unit. Now Alice and Bob are in the city 1. They want to arrive at the city n. But they do not want to arrive at any cities at the same time (except city 1 and city n). And they also do not want to take the same vehicle. Alice will take the bus and Bob will take the train. Could you find the minimum time that Alice and Bob both arrive at the city n? If some of them can not arrive at n or they have to meet some cities at the same time, print -1.

All cities are labeled from 1 to n.

Note: There are no multiple roads or railways between two cities.