strategic-warehouse-placements

A big international retailer is setting up shop in India and plans to open stores in N towns (3 ≤ N ≤ 1000), denoted by 1, 2, . . . , N. There are direct routes connecting M pairs among these towns. The company decides to build warehouses to ensure that for any town X, there will be a warehouse located either in X or in an immediately neighboring town of X.

Write a program to find the minimum number of warehouses the company has to build.

[Input]:
Input will be given in the following format 
N M
S1 E1 (Start Pt and End Pt of a direct route)
S2 E2
S3 E3
....
SM EM
Each route is bidirectional
No combination of towns will be repeated.  

[Output]:
Output should be in a file in the following format
Wx - Minimum # of warehouses

*Problem provided by JDA

SAMPLE INPUT
10 7
1 2
2 4
2 5
3 6
8 6
9 7
10 7

SAMPLE OUTPUT
3

Source: hackerearth | Difficulty: EASY


Solutions: