Problem F
Accomplices
Your friend Alex is a master of pranks and has been scheming his magnum opus prank: a prank so elaborate that it requires an entire team of accomplices. However, to maintain secrecy, X has imposed a strict condition:
-
No two recruited accomplices can be friends with each other.
This way, if one of them is caught, they cannot directly expose any of the others.
You have been tasked with analyzing all possible ways to recruit a group of accomplices while ensuring this condition is met. Specifically, Alex wants to know how many distinct ways there are to form such groups of different sizes.
You are given a set of $n$ candidates numbered $1$ through $n$, along with a list of friendships between them. Each friendship is bidirectional—if candidate $a$ is friends with candidate $b$, then candidate $b$ is also friends with candidate $a$.
Your job is to determine, for each possible group size from $0$ to $n$ the number of ways to form such a group while satisfying X’s constraint.
Input
The first line contains two integers $n$ and $m$ $(1 \leq n \leq 20$, $0 \leq m \leq \frac{n(n-1)}{2})$—the number of candidates and the number of friendships.
Each of the next $m$ lines contains two integers $a$ and $ b $ $(1 \leq a, b \leq n$, $ a \neq b)$, indicating that candidates $a$ and $b$ are friends. There are no duplicate friendships.
Output
Print $n+1$ integers on a single line, where the $i$-th integer represents the number of ways to form a valid group of exactly $i-1$ accomplices.
Sample Explanation
We can denote a group of candidates as a list like $[1,2,4]$, representing the group of candidates $1$, $2$, and $4$. In the first sample, this list is not a valid group for the prank because candidates $1$ and $2$ are friends. The groups for the sample are as follows.
-
With $0$ accomplices there is $1$ way to select a group: $[]$.
-
With $1$ accomplice there are $5$ ways to select a group: $[1]$, $[2]$, $[3]$, $[4]$, and $[5]$.
-
With $2$ accomplices there are $7$ ways to select a group: $[1,3]$, $[1,4]$, $[1,5]$, $[2,4]$, $[2,5]$, $[3,4]$, and $[3,4]$.
-
With $3$ accomplices there are $2$ ways to select a group: $[1,3,4]$, and $[1,3,5]$.
-
With $4$ accomplices it is impossible to select a group where no two candidates are friends.
-
With $5$ accomplices it is impossible to select a group where no two candidates are friends.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 3 1 2 2 3 4 5 |
1 5 7 2 0 0 |
