Business Expansion

Yeonjong, the head of the successful venture company "Bong Corp.", decided to expand the business to the United States.

He flew to the United States to meet investors in LA. When he got off the plane, however, he was in New York instead. His secretary only knew one American city, New York, and naturally booked the flight there.

To keep the cost of reaching LA as low as possible, Yeonjong will rent a car instead of taking another plane.

There are N cities in the United States, numbered from 1 to N. There are also M roads. Each road connects two cities and can be used in only one direction.

New York is city 1, and LA is city 2.

Because Yeonjong's company is extremely valuable, he must hire guards in every city he visits. Once guards are hired in a city, they do not need to be hired again even if he visits that city multiple times.

Yeonjong starts from city 1, visits city 2, and then returns to city 1. Find the minimum number of guards he must hire.

The first line contains the number of cities N and the number of roads M. (2 <= N <= 100, 2 <= M <= 200)

Each of the next M lines contains two distinct integers A and B. (1 <= A, B <= N) This means there is a road from city A to city B.

The same road is never given more than once, but the road in the opposite direction may also be given.

Print the minimum number of guards Yeonjong must hire while traveling from city 1 to city 2 and then back to city 1.

The input is always such that at least one valid route exists.

In the first public test, he can travel in the order 1 -> 3 -> 4 -> 2 -> 6 -> 3 -> 4 -> 5 -> 1. The distinct visited cities are 1, 2, 3, 4, 5, and 6, so the answer is 6.