P6691 Multiple-Choice Question

Xiao L likes logical reasoning. One day, he found a strange problem in a logic book written by the British philosopher Wo Xiede called *A Logic Book Whose Name I Also Don’t Know Why It Is Called Like This*, but he could not solve it. He knows you are good at using programs to solve problems, so he decided to ask you for help.

This is a multiple-choice question with $n$ options, and the statement of each option is unique. The content of option $i$ has the following form: - Option $a_i$ is true / false. Xiao L thinks that the answer to this kind of question may not be unique, so he wants to ask: how many valid answers does this question have (it is allowed that all options are true or all options are false). He also wants to know, among all these answers, how many true options the answer with the most true options has, and how many true options the answer with the fewest true options has. Of course, if this question has no valid answer, you can directly reply to Xiao L with `No answer`.

The first line contains a positive integer $n$, representing the number of options. The next $n$ lines each contain two integers $a_i, opt_i$, describing an option. When $opt_i = 1$, it means the content of this option is **Option $a_i$ is true**; when $opt_i = 0$, it means the content of this option is **Option $a_i$ is false**.

If no answer satisfies this multiple-choice question, output `No answer`. Otherwise, output three lines, each containing a positive integer: the number of valid answers, and the numbers of true options in the valid answer with the most true options and in the valid answer with the fewest true options, respectively. The number of valid answers should be taken modulo $998244353$.

For Sample 1, there are $2$ valid answers in total: - Options $1, 2, 3$ are true. - Option $4$ is true. Among them, the answer with the most true options has $3$ true options, and the answer with the fewest true options has $1$ true option. ### Constraints For $10\%$ of the testdata, $n \leq 10$. For $30\%$ of the testdata, $n \leq 100$. For $60\%$ of the testdata, $n \leq 10^3$. For $100\%$ of the testdata, $n \leq 10^6$, $1 \leq a_i \leq n$, $i \neq a_i$, $opt_i \in \{0, 1\}$. Translated by ChatGPT 5