50025. Independent People

I'm a slow walker, but I never walk backwards.

Problem Description

Read problems statements in Mandarin ChineseMorris AI 翻譯:
有 $n$ 個人,編號從 $0$ 到 $n-1$,請問能不能找到一組恰好為 $m$ 個人的群組,他們彼此都不認識。如果存在多組解,輸出任一組即可。反之,無解則輸出一行 no solution

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.

Subtasks

  • 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 2
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
4 2
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0

Sample Output

0 2
1 3

Discussion