50025. Independent People

Problem Description

Given a set of $n$ people, could we find a subset of size $m$ among them so that any two persons from this subset are NOT friends? Consider the following example, We index the people from 0 to 3. Let 0 and 1 be friends, 1 and 2 be friends, 2 and 3 be friends, and 3 and 0 be friends. If $m$ is $2$ then both $\lbrace 1, 3\rbrace$ and $\lbrace 0, 2\rbrace$ are solutions. If $m$ is $3$ then we cannot find any solution. If there are no solutions, print no solution.

• 15pt. $m = 2$
• 15pt. $m = 3$
• 30pt. $n$ is no more than $16$, $m$ is between $2$ and $n$.
• 40pt. $n$ is no more than $100$, $m$ is between $2$ and $n$.

Hint

At every level of recursion you want to keep track of people you have chosen, so that you do not choose their friends in the next level of recursion. If you can reach level m that means you have already chosen m people that that are not freinds. This is very similar to the n-queen in the textbook.

Sample Input

4 20 1 0 11 0 1 00 1 0 11 0 1 04 20 1 0 11 0 1 00 1 0 11 0 1 0


Sample Output

0 21 3