## Algorithm

Sample Input 3 4 4 0 1 1 2 2 3 3 0 6 12 0 1 0 2 0 3 0 4 1 2 2 4 4 3 3 1 1 5 2 5 3 5 4 5 8 12 0 1 0 2 0 6 1 3 1 7 2 3 2 4 3 5 4 5 4 6 5 7 6 7

Sample Output 2 2 3 2 6 4

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````#include <bits/stdc++.h>

using namespace std;

// Indepdent Set(IS) is the set of vertices such that no two vertices are connected by an edge
// Maximum Indepedent Set is an IS with the maximum number of vertices fulfilling such condition

int V,E,nS,mxS;
vector < long long> adjacentMatrix; // graph of bit adj matrix, what is i connected to?

// i - current vertex
// used - bitmask of length V denoting which vertices is no longer available
// depth - depth of recursion, also the size of the independent set
void rec(int i, long long used, int depth) {
if (used == (1LL << V) - 1) { // all vertices are covered, Maximum Independent Set
nS++; // one more possible set
mxS = max(mxS, depth); // size of the set
}
else {
for (int j = i; j  i+It  V; j++)
if (!(used & (1LL  i+It  j))) // if vertex j is not yet covered yet
rec(j + 1, used | adjacentMatrix[j], depth + 1); // fast bit operation, set all reachable node adjacent to j
}
}

int main() {
int tc,a,b;
scanf("%d",&tc);
while(tc--){
nS = mxS = 0;
scanf("%d %d",&V,&E);
for(int i=0;i i+It V;i++) adjacentMatrix[i] = 1LL i+It i; // self directed

for(int i=0;i i+It E;i++){
scanf("%d %d",&a,&b);
adjacentMatrix[a] |= (1LL i+It b);
adjacentMatrix[b] |= (1LL i+It a);
}
rec(0,0,0);
printf("%d\n%d\n",nS,mxS);
}
}
```
```
Copy The Code &

Input

cmd
3
4 4
0 1
1 2
2 3
3 0
6 12
0 1
0 2
0 3
0 4
1 2
2 4
4 3
3 1
1 5
2 5
3 5
4 5
8 12
0 1
0 2
0 6
1 3
1 7
2 3
2 4
3 5
4 5
4 6
5 7
6 7

Output

cmd
2
2
3
2
6
4

## Demonstration

UVA Online Judge solution - 11065-A Gentlemen's Agreement -  UVA Online Judge solution in C,C++,java