410787: GYM104114 C COVID

During the standard yearly testing, $$$n$$$ people are being tested for COVID.

Because of the limited amount of available tests, a procedure called batch testing is in place. More specifically, for each of the available $$$m$$$ tests, a subset of people is selected and they are tested as a group. If any of the people of the group is positive, the test will yield a positive result (and similarly, if none of the tested people are infected, the test will yield a negative result).

More specifically, test $$$i$$$ ($$$1 \leq i \leq m$$$) is done on the group of people with IDs $$$a_{i,1}, a_{i, 2}, \ldots, a_{i, k_i}$$$. All $$$m$$$ tests are perfect (they always yield positive if and only if at least one person of the group is positive), and they, unfortunately, all came back positive.

Before testing, each person was expected to have a $$$50\%$$$ probability of being positive. Additionally, all of the probabilities of having COVID were independent (i.e. one person having / not having the disease did not influence the probability of someone else having it). However, given the $$$m$$$ positive test results, some people are now more likely to have COVID than others, and it is crucial for the medical team to figure out what is the new status.

Sort the people from least probable to have the disease, to most probable, after the batch testing procedure.

Tip: It can be proven that the posterior probability of person $$$i$$$ ($$$1 \leq i \leq n$$$) having the disease is proportional to the number of scenarios (out of the $$$2^n$$$) in which all $$$m$$$ tests output the correct result, and person $$$i$$$ is positive.

The first line of the input contains two integers $$$n, m$$$ ($$$1 \leq n \leq 1000, 1 \leq m \leq 15$$$)  — the number of people and the number of available tests, respectively.

The following $$$m$$$ lines describe the tests. The $$$i$$$-th of them ($$$1 \leq i \leq m$$$) starts with an integer $$$k_i$$$ ($$$1 \leq k_i \leq n$$$), the number of people in the test group, followed by $$$k_i$$$ numbers between $$$1$$$ and $$$n$$$, representing the people tested in the $$$i$$$-th test, in increasing order.

Output $$$n$$$ numbers, representing the IDs of the $$$n$$$ people, sorted from least probable to most probable to have COVID. People with equal probability should be sorted in increasing order of IDs.

5 2
2 1 2
3 1 3 4

5 3 4 2 1 

6 2
3 1 3 6
3 2 4 5

1 2 3 4 5 6 

In the first example, the probabilities of the $$$5$$$ people are $$$\frac{8}{11}$$$, $$$\frac{7}{11}$$$, $$$\frac{6}{11}$$$, $$$\frac{6}{11}$$$, $$$\frac{1}{2}$$$.

In the second example, all probabilities are equal to $$$\frac{4}{7}$$$.