Maximum Clique and Independent Set in an Undirected Graph

Given an undirected graph \(G\), you are required to compute the following:

1. One maximum clique of \(G\).
2. The number of maximum cliques in \(G\).
3. One maximum independent set of \(G\).
4. The number of maximum independent sets in \(G\).

A maximum clique is defined as a largest complete subgraph of \(G\), where a complete graph is one in which every pair of vertices is connected by an edge. A maximum independent set is defined as a largest set of vertices in \(G\) such that no two vertices in the set share an edge.

inputFormat

The first line contains two integers \(n\) and \(m\) \( (1 \leq n \leq 20)\) representing the number of vertices and edges, respectively. The vertices are numbered from 1 to \(n\).

Each of the next \(m\) lines contains two integers \(u\) and \(v\) which indicate that there is an undirected edge between vertex \(u\) and vertex \(v\).

outputFormat

Output four lines:

1. The vertices (in increasing order) of one maximum clique of \(G\), separated by a single space.
2. The number of maximum cliques in \(G\).
3. The vertices (in increasing order) of one maximum independent set of \(G\), separated by a single space.
4. The number of maximum independent sets in \(G\).

sample

3 3
1 2
2 3
1 3

1 2 3
1
1
3