P1692 Tribal Guard

In the primitive Byteland tribe, residents often clash over limited resources. Almost every resident has enemies. To organize a force to defend the tribe, the chief wants to select as many residents as possible so that no two selected people are enemies. Given the enmity relations among residents of the Byteland tribe, compute the optimal composition of the tribal guard. If multiple solutions are feasible, output the lexicographically largest one.

The first line contains two positive integers $n$ and $m$, indicating that there are $n$ residents in the Byteland tribe and $m$ enmity relations. Residents are numbered $1,2,\cdots,n$. Each of the next $m$ lines contains two positive integers $u$ and $v$, indicating that residents $u$ and $v$ are enemies.

The first line is the number of people in the tribal guard. The second line contains the composition $x_i$, $1 \le i \le n$, where $x_i = 0$ means resident $i$ is not in the guard, and $x_i = 1$ means resident $i$ is in the guard.

For $60\%$ of the testdata: $n \le 20$, $m \le 100$. For all testdata: $n \le 100$, $m \le 3000$. The testdata are uniformly sampled at random from all valid instances. Translated by ChatGPT 5