This question is from past contest of Expedia contest on InterviewBit, which is over now.

There are N cities numbered 1 to N. From each city, there are exactly N flights connecting to other cities. Srijesh hates travelling on flights but he had no other option as he has to reach city N from city 1. You are given the details of flights from each city i.e. if there are 3 flights from city ‘x’ say(‘A’,‘B’,‘C’) then there are 3 flights from city x that will go to city ‘A’,‘B’,‘C’.

Find the minimum number of flights he has to take to reach city N from city 1.

If there is no possible way to reach city N from city 1, output -1.

**Constraints:** 1<=M<N<=1000 1<=A[i][j]<=N

Example- A=[[2,4],[4,3],[5,2],[3,1],[1,4]]

Output- 3.

Explanation- He can choose flights from city 1->2, 2->3 and 3->5. He can also choose flights from city 1->4, 4->3 and 4->5. The minimum number of flights taken is 3.

Can anyone help in this question?