Maximum Independent Set in a Cactus Graph

You are given a simple undirected graph \(G=(V,E)\) with the special property that every edge belongs to exactly one simple cycle. Such graphs are known as cactus graphs. Your task is to compute the size of a maximum independent set of \(G\). An independent set is a set of vertices such that no two vertices in the set share an edge.

Note: Although in general the maximum independent set problem is NP‐hard, the given restriction on the graph guarantees that each edge is in at most one simple cycle, and in our input the number of vertices is small (\(n \le 20\)). This allows you to solve the problem by using an exponential backtracking (or bitmask) approach.

Mathematical formulation:

Find \(S \subseteq V\) such that for every edge \((u,v) \in E\) we have \(\{u,v\} \not\subseteq S\), and maximize \(|S|\).

The graph is guaranteed to satisfy:

[ \forall e \in E, ; e \text{ belongs to exactly one simple cycle}. ]

inputFormat

The first line contains two integers \(n\) and \(m\) (\(1 \le n \le 20\), \(0 \le m \le \frac{n(n-1)}{2}\)): the number of vertices and edges respectively. The vertices are numbered from 1 to \(n\). Each of the following \(m\) lines contains two integers \(u\) and \(v\) (\(1 \le u, v \le n\), \(u \neq v\)) representing an undirected edge between vertices \(u\) and \(v\).

outputFormat

Output a single integer: the size of a maximum independent set of \(G\).

sample

3 2
1 2
2 3

2