{"problem":{"name":"HonestOrUnkind2","description":{"content":"There are $N$ people numbered $1$ to $N$. Each of them is either an _honest_ person whose testimonies are always correct or an _unkind_ person whose testimonies may be correct or not. Person $i$ gives","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc147_c"},"statements":[{"statement_type":"Markdown","content":"There are $N$ people numbered $1$ to $N$. Each of them is either an _honest_ person whose testimonies are always correct or an _unkind_ person whose testimonies may be correct or not.\nPerson $i$ gives $A_i$ testimonies. The $j$\\-th testimony by Person $i$ is represented by two integers $x_{ij}$ and $y_{ij}$. If $y_{ij} = 1$, the testimony says Person $x_{ij}$ is honest; if $y_{ij} = 0$, it says Person $x_{ij}$ is unkind.\nHow many honest persons can be among those $N$ people at most?\n\n## Constraints\n\n*   All values in input are integers.\n*   $1 \\leq N \\leq 15$\n*   $0 \\leq A_i \\leq N - 1$\n*   $1 \\leq x_{ij} \\leq N$\n*   $x_{ij} \\neq i$\n*   $x_{ij_1} \\neq x_{ij_2} (j_1 \\neq j_2)$\n*   $y_{ij} = 0, 1$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$A_1$\n$x_{11}$ $y_{11}$\n$x_{12}$ $y_{12}$\n$:$\n$x_{1A_1}$ $y_{1A_1}$\n$A_2$\n$x_{21}$ $y_{21}$\n$x_{22}$ $y_{22}$\n$:$\n$x_{2A_2}$ $y_{2A_2}$\n$:$\n$A_N$\n$x_{N1}$ $y_{N1}$\n$x_{N2}$ $y_{N2}$\n$:$\n$x_{NA_N}$ $y_{NA_N}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc147_c","tags":[],"sample_group":[["3\n1\n2 1\n1\n1 1\n1\n2 0","2\n\nIf Person $1$ and Person $2$ are honest and Person $3$ is unkind, we have two honest persons without inconsistencies, which is the maximum possible number of honest persons."],["3\n2\n2 1\n3 0\n2\n3 1\n1 0\n2\n1 1\n2 0","0\n\nAssuming that one or more of them are honest immediately leads to a contradiction."],["2\n1\n2 0\n1\n1 0","1"]],"created_at":"2026-03-03 11:01:14"}}