Curses! A handsome spy has somehow escaped from your elaborate deathtrap, overpowered your guards, and stolen your secret world domination plans. Now he is running loose in your volcano base, risking your entire evil operation. He must be stopped before he escapes!

Fortunately, you are watching the spy's progress from your secret control room, and you have planned for just such an eventuality. Your base consists of a complicated network of rooms connected by non-intersecting tunnels. Every room has a closed-circuit camera in it (allowing you to track the spy wherever he goes), and every tunnel has a small explosive charge in it, powerful enough to permanently collapse it. The spy is too quick to be caught in a collapse, so you'll have to strategically collapse tunnels to prevent him from traveling from his initial room to the outside of your base.

Damage to your base will be expensive to repair, so you'd like to ruin as few tunnels as possible. Find a strategy that minimizes the number of tunnels you'll need to collapse, no matter how clever the spy is. To be safe, you'll have to assume that the spy knows all about your tunnel system. Your main advantage is the fact that you can collapse tunnels whenever you like, based on your observations as the spy moves through the tunnels.

Constraints

~1 \le N \le 50~

~1 \le M \le 10^3~

The test data are not the official test data used at the World Finals. The data as a result may be weak. If you wish to augment the test data to break unintended AC solutions, please open a ticket by clicking the "Report an issue" button at the bottom of the page, and putting test cases in the ticket.

Input

The first line of input will consist of two space-separated positive integers, ~N~ and ~M~, which are the number of rooms and number of tunnels respectively. Rooms are numbered from ~1~ to ~N~. ~M~ lines follow, each with two integers ~x~ and ~y~, which are the room numbers on either end of a tunnel. A 0 indicates the tunnel connects to the outside. More than one tunnel may connect a pair of rooms.

The spy always starts in room 1.

Output

Print a single line containing the minimum number of tunnels to collapse.

Sample Input 1

4 6
1 2
1 3
2 4
3 4
4 0
4 0

Sample Output 1

2

Sample Input 2

4 6
1 2
1 3
1 4
2 0
3 0
4 0

Sample Output 2

2

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

---