Polling Stations

Interview

Time limit1sMemory limit64 MB

Summary

Given an undirected graph, find the smallest set of vertices such that every edge touches at least one chosen vertex.

Level: Medium5 of 10
Topics: Graph, Greedy
Solved: No attempts yet

Problem

The Kingdom of Byteland decided to hold a vote. To take part, an inhabitant travels to the nearest town that has a polling station. Everyone is supposed to vote, but most people are very lazy and will not go if every polling station is more than one day of travel from their home town. Many people in the countryside live along the roads, so for every road at least one of the two towns it connects must have a polling station.

The king wants to choose as few towns as possible. Find the minimum number of towns that must have a polling station.

Input

The first line contains two integers $n$ and $m$ ( $1 \le n \le 50$ , $1 \le m \le 1000$ ), the number of towns in the kingdom and the number of roads. Towns are numbered from $1$ to $n$ .

Each of the next $m$ lines contains two integers $a_i$ and $b_i$ ( $1 \le a_i, b_i \le n$ , $a_i \ne b_i$ ), meaning that a road runs between towns $a_i$ and $b_i$ and takes one day to travel.

Output

Print the minimum number of towns that must have a polling station.

Examples2

Example 1
Input
```
4 4
1 2
2 3
3 1
1 4
```
Expected output
```
2
```
Example 2
Input
```
2 1
1 2
```
Expected output
```
1
```