Minimum Vertex Cover Problem

You are given an undirected graph with n nodes and m edges. Your task is to determine the minimum number of vertices needed to form a vertex cover for the graph, i.e. a set S of vertices such that every edge in the graph has at least one endpoint in S. In mathematical terms, for every edge \( (u,v) \), either \( u \in S \) or \( v \in S \) (or both).

Note: The input size is small enough so that a brute-force solution (checking all subsets) will pass within the time limits.

inputFormat

The input is given from standard input and consists of:

• The first two integers n and m, representing the number of nodes and edges respectively.
• Followed by 2*m integers where each consecutive pair represents an undirected edge between two nodes.

Nodes are numbered from 1 to n.

outputFormat

Output a single integer: the minimum number of vertices required to cover all edges in the given graph. The output should be printed to standard output.

## sample

5 6
1 2
1 3
2 3
2 4
3 4
4 5

3

</p>