Problem:


Score : 300 points

Problem Statement

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 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.

How many honest persons can be among those N people at most?

Constraints

All values in input are integers.

1 \leq N \leq 15

0 \leq A_i \leq N - 1

1 \leq x_{ij} \leq N

x_{ij} \neq i

x_{ij_1} \neq x_{ij_2} (j_1 \neq j_2)

y_{ij} = 0, 1

Input

Input is given from Standard Input in the following format:

N
A_1
x_{11} y_{11}
x_{12} y_{12}
:
x_{1A_1} y_{1A_1}
A_2
x_{21} y_{21}
x_{22} y_{22}
:
x_{2A_2} y_{2A_2}
:
A_N
x_{N1} y_{N1}
x_{N2} y_{N2}
:
x_{NA_N} y_{NA_N}

Output

Print the maximum possible number of honest persons among the N people.

Sample Input 1

3
1
2 1
1
1 1
1
2 0

Sample Output 1

2

If 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.

Sample Input 2

3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0

Sample Output 2

0

Assuming that one or more of them are honest immediately leads to a contradiction.

Sample Input 3

2
1
2 0
1
1 0

Sample Output 3

1



Sample input:
3
1
2 1
1
1 1
1
2 0


Sample output:
2

Submission status: Accepted

Solution code:
import subprocess
import gzip, base64, os
import stat

gz = b'H4sIANEl7V0C/+19f2AU1bX/7G5+LL+yAVEjPwOuCCIhC+FHFHVDWJiVDUQSkKqwSTYbEtlk83ZnIbGoaBLrdgml1lpfX2up71uf/fFe1bYWqeWHSIKKiqiIUCFa0FkCgr8girDvnHvvbO7MzkSo/b6/ukrunM+ce++555577o+Zufdel2eu2WQSlJ9ZuFFA6pYRTkI7Gf6oL8kC2EyhH/wdLYwQMoBO5/icglMV9rCkldDK+CzwLw3+zTRTeqbZqQpHMD4lNHFhusD/nKrw+e8IqlAQcpPxUNb9yyi6f1mFKsxNo3h+pjqemcXrYfF6GL8SCmZBFSrlS2P/yhlezsqlhHMY3xyOH3+lR6VqvN5VRuldZU5VuIbxrdHEuwXiZQgX/stm4SKWn5FexjP5lVCph8mBuqrpBZMD1ZMCdQ2RpklNM6dPml6QFw7mTSEyZTPeeQsWq/SYw2QeymwA7z+797ZfiQ8Gum2j/i10yaH7wtmvTi7De9ezeFglbQ3ZtWlj+plNQoGwFpLGezfCv2L498zfpr7d/74N3p/7/rpzfX1i14NtvsveKtvYsu47zk8mfeJdnpW7Kn+8623PtmPjtg19dGDxYyMaNzW7Vz7bl36OgABDdPA3zfr4dRn6+GSTPv6MoI9nJy1P/RttgL+erp/O3Qb4Kwb5thvwLzEoV6YB7jfAv5emj9cZ5DvJIJ2ZBvr/kwF+hUE6Uw30ucIgndUG6XxqwD/OgH+hQb4/MqiXdAP7KTfId7MB/yADeSoM+JcZ8J82aBdjDNJ5wqDenzPANxukf4+BfuoM9FlkIP9oA7zZQJ9DDfj/x6C89QbyLzRI57hBuQoN0jlkoDfJAH/ZQM6PDdrd1QZ62GuQ/msGcooG5f2rQb5XQjpjhGHCU1W038lh+BCGn/JVqPqtq9MpLlRTfCnDB6QxnKWzluG/YvnmDnOq8p3H9HNKg8+HfAdDOl0sfcXG7kqjuOCvUPWH75povmur1Pw2ps9tV6jTL02n6WysUqdzA0u/i+HZ7MY8Vq6Kak25mP43DFenL0D/HJaqfRMnYp88XfB6V9QHG7xhqTIkeb2C9+ZV3kX+FXVhyR8qDlSGw/6w4HWXl3ir/SEGl5cUB4IN/vLKqoCf3tO/422UakP+ymrvSn+z1wdXEoK+pkpvTcjv9/qbfP5GqS7YIHhvW1AWLoBsGx35XswpLIWCza5F88sq3T4XuR0shBt1DWF/SHIHXK5FZcFyL96YXyZN80nNjX5gdEwFntV11f4G4KyTXKuAoUxyzPB6QY7gam8ViFIZCAR9q2jMsGNqTV1DtbemLhSWvMEaV+l8X309zW5aTSASrlWSmM4n4asMSyQFuDE1FGmQ6uqhMKFQMDTHwUUIQiH8lfWK0D5AHb7aypBXClXWSWGQF0oBKVRVhut8Cre73Fue73WVTfeWzi+b6g0wfZHMScqFoOX6ugZQJRUhXOxAPYWJ3OXlkGBhb4J1DStYsjq5E91S5Uoz64JhKFvYX+AGxbFiAD4dlFUZ8PcCmgKzzJOSgAL5SkOoXoVITDrIT1cj03wBf2XIBXemeN0gE/yTiNlA0afkK7UQjGB1eUOVDSv8kKVSm9NJbYLNSt6GoLpC8fYMrrI198vdIBlvjwhoysqqogpMvQFsQPLVcnYLspV5/fWNUjO0hUZoTMFQ5Qq/i1moYxotNa2SqkiNcX1MBR5UtndFU5O30R8KBxsqA3WQ7Kp8psCkmHOmsFoJg7JKvKC4lV5IsVpBp1c2NvobqkkhAakOlK6CqpAKoexEixKWc8lFSUfqocAH+k+NC2ZmEBejNayuJ5FnsNw53RWC6qh3cNXXq4wlaZa0qET/pAEDr8Z9BKc2RiSXj1npxbUBsFKsbWJwC0Fl9cFqPynfAnBHkGlTZVXdKgeaX7jO60Of6EWPAy27JujinZcDSsLaZ4AVOkXjwDwj5AeXsAqKq9f6illjm8/XdcHq2kpJW7Gs6WHFolOvp/4crlb4oEaQcgjexQ2r0ewX+cORej/e9FG2miCkIYBqpGBAqPEHa4SaFX4pLPiIgvFGAO4znUv+pjpJqPfXh/0k8NU3kqCxWajxBYJhv1BPowFYH1yFbh5zYp1KfWVdg4AuX5hXXOydmpcvzPO4Zxd7p+Q5CpKXU/KmCcVLlxbNdnsdeVMpvHQpcBfkORwqspCn6AzSDDNGM5vxIpVOEAtBzcm/Aru2MC6KprH7ZpiFmslM1MK4Mhh/BrufyUIrx5/6X0ZyPcIkdKX3zttKxzUPwBnrmgzlvlk4x+7nw7+Hf/hIBq4StGZQLDKsrh/K8oMkfxoZCyjjnDd/vzIdZ87/wfgre35ixhWQJxgdvXeCGWfUf2K0NOEhK5Z7B0uvx0vHCxnsX/LHxhfpbB6t/NZyeDGHb+RwF4c/xeHXc3gXh8/lcGUch/gsXp7qXvwGfn7C4fP49Dm8SDUB7cVnc3BOBcUzubEWGadxuJnDx3O4hcPzOTyNn5dyOL8+5eRwXv8ih1v5cSGH9+PwpRzen9cPhw/g8FoOH8jhjRw+iMObODyLtwcOt3H4gxyezeEbOHwwhz/K4fz4fyOHX8LhT3L4UN7eOHwOh2/i8Ms4fBuHX87huzg8h8P3cPgVHL6fw4fzdsjhN3G4zOEjePvn8JEc3sPho3h7ruzFR3OwlcP5+W82h4/h7Z/Dx/L2z+FX8vbP4Xbe/jn8Kt7+OXwcb/8cfjVv/xzOz1xKOXwCb/8cfg1v/xw+kbd/Dr+Wt38On8TbP4fn8fbP4ZN5++fwfN7+OdzB2z+Hi7z9c/gU3v45fCpv/xxewNs/h0/j7Z/Dp/P2z+EzePvn8Jm8/XN4IW//HH4dX78tx61iLP3H83IFsW2blC6HCfiidYd6mpqYdj+wJK5qhb+20U64QroWb8W7EvC76i6k0WXH9xA6hDS66vg2Qt+JNLro+FOErkIaXXN8I6FvQxpdcnwDoRchja44vpbQNyON4scbCT0baXTJ8QpCX4c0uuJ4KaGnII0uOO4k9DVIo+uN5xN6LNLocuO5hB6GNLraeDahhyCNLjYuELo/0uha46fOI21GOpuUn9BfzQV6MCk/oT9FeggpP6GPIX0JKT+hP0B6KCk/oQ8gfSkpP6H3In0ZKT+hX0b6clJ+Qr+AdA4pP6E3I30FKT+hn0F6GCk/oX+D9HBSfkI/jvQIUn5C/xTpkaT8hH4I6VGk/IT+PtKjSfnPIX0/0rmk/IS+C+kxpPyEDiE9lpSf0HcifSUpP6GrkLaT8hP6NqSvIuUn9CKkx5HyE/pmpK8m5Sf0bKTHk/IT+jqkJ5DyE3oK0teQ8hP6GqQnkvITeizS15LyE3oY0pNI+Qk9BOk8Un5C90d6Min/16T+kc4n5Sf0Vy6gHaT8hP4U6Smk/IQ+hvRUUn5Cf4B0ASk/oQ8gPY2Un9B7kZ5Oyk/ol5GeQcpP6BeQnknKT+jNSBeS8gNdujUNRljyUbjcimtaW5DcfAq8gOyA4izd4Tjhjr6xXIx+ILYcOVVa7u7cVlrqFMTO7V0LMeh0jnQK8j6I/rltNHTgmxIQdbE4qQcCsaUnS4weXW1etmMT8SHgOD5fthVvJbpso8mS16Yejn97jwX4xegL4vZjN4mmPeIbPRGIvJlG3guRxWgHjf8Bi7/2hv4iGFdk8GKIKd8DBVzWkX4Gmpzpsx3of8SWG/Y7gUEalRRh6OKtp5ZBbtGjiT3L4t+FKLbRQjxMw8VFtxYtKVpcVF4m3ncc3dJWbDpbcBgqZ0MpxegOl+O02HZQGi+2P2x/Cm+uRYVED8tYf2JnsRWdG4RkGOWOHuJSeO0sprBTbDshFWN0lGnLL0n0k/J9JLqLRBM7W+0PKq43+jv7owRzWdFPds6xk9XR7lwVF1w/qnQqpijwOE54on+0bwS6pO20lOZOzLV6opK9gpPnxrOsRAks0SSxfZ19G97EEmzuT/I+LDef1SvWYU/0efuTcOmJRYAtYC91fT+PS/rvXyUS7uiLHPLGV6TwjoNY/ClFtmd3tvQsjljciQ5UxS6S20lP9LTcRDJ0sQyZQqLdYixgrxBjdwtibKpcTpJPs6Pc/cXEfKutdRw4XTcoh8TDCxLRE/1/REfulll2wda6DjxpR6t9A04bYqCk1m1i7A57aeRKTCMyUoxZxPYm+TmcjoiFr9va9tioEh7+EmQCue1iosQaGSXGXIKa8UbCeFJeiYztz9vROsX2P5K85SWjkKCgXDcJOXeiznLE2M8oJxRjMhFhQooIQ5gIgzFlqGVlqXhrblK1q74k9ejYhulcA2KItt8nxO0fWeQR5I6lo9hK6o7VYQ5V6X4R7AS69Rwxegxi7MU2Nljc/oFlS4LV/bIejH6HPRfKblv/IZgE5AGRssX2Ofam7iKxZVvPc7RhvSRd8Rx2gKds263RdfZqMNUYDbozY9b2WxLR7LaX7i1HnVQAKFeBZN0ukBrySSpq0kiar+taDOfY87F2mrBU1xLtjEvRzl0JlPCw/NkZ1A4IRUcra+z5gm39MBBYjKG4tt/vFBO7MMnxjoPxGhPy9Ipua92Oz7D0xY//TtBy/7EP7l+kcP9XH9wPpXD/tA/uNpwdd85lTXDU99P/G3xb0YNzRuXE70I2Rc22H/zKTM2PqPoM6Cb+IzXDmxkcwz5k2J6hYjjAM/wJGXapGRZbOYaHkQGMTKghvzzb6FbqltrX2GuT1btgOFbrHfaZnFvYfJrYLtRx0Vby5Gv8lhh1qOgWnJj4ijMGHmiN3cml1Nib0l9TUxIxpZG6Kb2HVlaLptXSJIOT+DOi6NZiC2THXrSuH59Gd9PhbjmfsLWi1xZjEz2mLxQmsfOFBLPD4V8QIbSyvfUFcYclbUdoKW2tHxDtFJvchR1FW3vAnG2t+AbDJhTNM+GUaNoB/QwVvRRFv5+k0FHSfk+O2HLWFGn8vguqPrN7lUrfJN+kLm2t+F6JmCi2grq6w9C/aeWaheK2bWOqv0XsFFAUsdPJVORkKursnuaJQsE+FqMH5P8CLW7CFgiy29pWwjihJDrLnup7S6IflaDPdBOf6U7xmc3Q43nAZ874HEYf45MyPfk5kek5msR57LREaYzt1m22wUmJIMxhEuZSZ7ZdjHrsjdDpxaCENYo+3LEZWEGe6BnwcXIWrRx3LEMsrJVt97dbMOa74oQ4euelZtTfaWSMQH1zWrrsc6X2pBvFWCvhJL1PJ71GnaUWfxPC3Tnq9sBiuxxHSqLnsC1UqHVyJwoBRWh0x4JW9/XBbGkE9juZnqgfI4ktO6Eug9a4CfigPt2xm8SoLE7owcETmMdzxHxscz5xmzpsD20TiSeB32gx+rKn8FPbQ9ut2z0216cwJCADIulqcZPCgrX5vSike3P7rC/IosdytLnYTSgKVv2E82L0E7Hl/R7RtF3K8ETHoECFJ22t1Od1gBAfW8REh2SjfCZSK19Jw3DYNUiMAWwVOzOpX7jVKraLVvTIpWLLebMIhrlUjJ613f9ruJ2sP+xXICbcNomdZhpzNsR6DbKzStli7C4gmiHV2Vbq+LdZ8Y5YuBNFiL4Q2YJte2n3rWL7Umv8Vxpve0Fd1qykk/v9p9BlTVK3t9hENPGriYmP0Zp45CE076WfoNOxUPl2gGzvRXZBPfaIEwNQ5JajPdhFlYrtd6Rnu2OTPTDMcWKVZ2E/Ht0pX4HRo7I7mumOeq03t6edckfnZXti0CrAILF4FSXRk9IYd8Jjt0aGuWNgl7wMPk/0I/mtU5BIy1kYmqw02do+hIYXf/ofUIbtBziJSirkMRAtvgCRi05nRYJLZwmmsxiQrevBYcvvgLDxapBR/jloPF5/DofmVN84lL3SnVgAYzVsxaqms7QH3ckZWT4JDqktgXwLCV+mmm854UvI206q3I7jFHWFW0i7+AZ/A00N/dJSrLpGMTZejDmJLVeA5dlaM0zEhOfQIWHTlRiC11kCDXpJtjQcx1kw0xkmtrwAjXmJNf68oPCXxG4Uo3s8tD0X/ZW2ZpfsNu3UtObXPIUfK635YzDBoueJ2OP45rxz9WpoyidIU/7RJ9SFxW5EOTwTvnJH97m3nwcx9ogtXT0eUxeKlIP6HQAG44mel/NBIfPb7/jcisq0osbWfwyaA8NbWhId544ut85vTzvujs7NRq8kFsLw3NY2ALLu7icfgbjd99dswP6/UX5kDHo+7GPbDuIwPsdwOHfqNO1G7R/T4VwtdeLgdTPF2EIr1A+dDdoWvC1aYDCHs8RYOYxPowNfANkxk5lSDhhITmSICGKnywdOUKvYC6GY2CFef4c937auGgcCZGSYYAPaQpmMaW3r6sDpbbHS6Yj8/EnSY3Bj7f4gGZkCbgO/Fs3pcFqJkTDjyGHGURIbp6QBUxc5QpLZySWz4wQmk2DJjNdPphNst4iMCIo2m+mQHAolRr/0QDlzbesfR/NoH3iO9oBnHSd4ZmJPHujdood7/ZX7DftxMTZUFk0wroEg5hDbTkeucCfSjouJNLl7pHb8BiOeCLjUl02EvWW7VUy8HnlOTOwsMb2CnuwxkeTQPUyx95fp5P1l8Y2vSnBOEX3j9HaTlAbXL4jtt5jElq8s4XehFM1Z7nbRBMOrli8tHlvxCwDZHtvuOO1u6TGvWd76UuQ2d2KX47Qnul0lT/ScO/ol5OJIkPxOv2CSLne3eY733DsWKl/uEfu94incseZSMdEpJl4FIcCV3vuuWHhetHnOiImXPNHX7928FR9nyRu70QbSfz0tF4zTCbp4co8PzBBmOq1Z0EmtvXumIKV/31XcPQwt4RnC7ULW/C10bnwysce25RRNLIwGG+2Uh5+gzmcsOJ/syAjsn4EaWLT2XqsQSZdnHae+Z043sp1GtgWE7UbGdg9hu/Q4NdqR3dRM0fChq06I2ZExYmwm8g5e2wSsA8A45Y+QC2dznfLxY3T6SYbb944g87X7XsSFjNuL7ihaVrS8yLtsh6bVRW7FFvcMxoTp6INCX9NoaMC21qfQU+Kcu+0JvIpdT1ta13Hadmshpfi6U+pewdZ6rI+Jzdsp06D3+uDelcK9pw/uv5C66pSfztWNOsJkHDXTRFohVtRw4lMuZRWVLrfEaQ19N44KRyf39Ah0ctAHxw+ZVBOlx85zXd1KohxAOIYXT3IMNyPDMydVDOd4hgnI0H0Ss4e20EkzLxhB+kZb62dYa9A/2trixHOq+8jW3Snlf7wP1bULqoJ89jEnxuNQ8Pj7gHSDcZwgWjpCBiW21jpIjYxGoK/FS82IxNb6s5T5d6iPWljGq/PeQUkJclkV9HyERujBRnJC8pMFGq8YfUW7RiPddNFDv968/iijbZ+U12Fe4PFYZybVk35shRh9VdOovlVuc2XakkZ9xPWCYjSOKYEXcBMvUEi9QDP1Aq/I7zPRoq/LH37IeYHmHGy+CflprLC8czgM6CTq6n5KL++XP0KtfiQ/DmnEf0HZSZeFAk0CweKXn1NsL4lfinjTeeoCxZG0wTkxJKPZ6A7Cicl2f4SOD1zsVmKoJWAjfyKGqpkctv5EOzz9NyMVeuPXJOi6KlsssrWS9VLiodaTSZe6agKqdOcapVugp57ffkjnrC1HmdHBzDreco5rrhzzPR/SelxylF+corFOxvNAX1vRu8oZH9FagekkejIyBSddTSN0uR1DsSoRl0cdpfWKxJbJtziFzfigSP7JkV5YhCZYQeqDm7+S/Mm6s63tdyY6C0Vmx4n4y9TFxV89x1SYXJC0tdnIvZPxp+GeXAWZxGWyHrijjw7u9qO0g/Md6bODKzhK2+6sI5waRxJr61CkU9tD3HKxa3a8gUpMrN+R6gMVQT7s5kn51qPoUTPJwC0JzgYwabXTkGO1hRpVpFg7bG1946IX/VCv3/la5eUzLdyCWjGq+wtzb12JUZegMhDNCjlZbVCZeVhl5iVGZn69nuW++HdquT/7QL3ojGI/flbf2jdAHHdnZmmZkyx2d6H5EfPOJG1lGRpVZBKWp4sYKgy52p9Pw+vYH8lbUi2vmeTbodzdV0JFkM4XRZjwd2rdJFL0EEzq5Qf+TjsiWaDr6vsxl1uOqGy+6gNlzcbWNozZPPK5HEfihcSwwdDSPRNh8BdVJBq0eCIbC0bXEcGw6JhJdlUFSSDfJPzz+pQKplvMoJFU3vP2XMhAvpy155lIHPiAWu6nEP7BREanB4h3Q9dJW7zWdT6TYo0PGltj9ypFM8qK1n6hzxUtdV6nU/La3Yfl/1nQ78oXv0+710ldiUTrQTrZHIwFj9GHTOBwbK34TRBO6W1tv8Ur9bT+W9XEvi6q4/85TGvkSWbt8dlmfXl/1UWmDlkTVNZz+YT/Q+sZ22VgPe++z1nPz7pUaxwlh7kHRR6yxGFR1sG34nxVXklqwkLX5uZnk5U7TzQXlz7T3QmciUTnW/EREltCZ6uv+93ReVZsa63vk36dDP72kY5dO/jblGIx6/uwzjWknbIZRtYh5pPRL/zyMPYwkOOhr5PDzTe/1htu7jRrc/wPs7GNPmBQ508fogOj6HvEza0FN7clF/5szl3oJAOsbUS5AXtpbzdyWD57iE6rNrKnfHeSHqT6nzlazDlEffWpv1GL2Kg8EoZsH/3/l+0v36PZNrNsH+WyZVNFHKxCtmOSFfhXJqqLxVGeXtNHsZE76UpoQsQRPLmM/fMazCeYZ2yNvVTuPIhz0zX2Chg5l0TPYN09fIhOtCtI5jfQS03mN6sytxtlPoQlWXRIv5usY3JUyDcdxCcnhHnoITL0cRyMD/tKP9qUv1Hz638QBytfJuj6h+p9BSsZwnwhRmfZi9bebRVsre+mYQu8O3vLUBgsOvY+h+tCshUFaOkBjzojXfWCw2RI2vESXZLSfxCEC/rYvKJWlyPR3a9mg/u+TgHfW1BWHe91t6dlijckLJgmZF5k85whY/tYNk5Us+UBB8kqq631fkGV9x8OKA/v2LM78uxLwifND9vlDBC78mDqszsRn92BPLGZYvRjefR79CH9NWQOaE99SL/bRFf1Ot5NJOh6FZVtpvw5JA5StRWSEVea3RPLx7lzrFaGBP/Clhzfa2nqEZoG4Lj14b+ho8nAx2lWsd0zMvH9EVauNEffVQbcbF12om3Lm+S1ClwQbF9nP4UlGn0g9UUHd/R4SfQkl9RP39UoZsu63oeaPZiMeEBXMe7YLFDBrTK+oFHS3iC7r18iR2z4gsU7B0hhH97RbaZvY+QQhQ1hz/R2Rpaikn65n/hXKZP4VunS1oMl0XP08Qe3nqhxtsASmY1m6tuPPTk+ybLaWvfBwD5+iLyF0dGTfBGnlhjNqSLb9gzoQ9PAeGM06L5V1dJq+JZG2GjQXa5iqzBiW1AUy2gXE0XRLCj0D8YkyAQO2xW+5SgfAEHjAxOqkfj17OEEYXgOGSaoGf58jmN4FBl+hQgq474XsRlyq23YgeGobU9y1NahO2q7KaWXulTTS3GFigvkEWRH993cnKV7Jd/z3Mfq73b6YKg8tV/8NGUZZpfJOMc/mPgJ0mF5zH5W4lgOuvo64up9F9HD8HWk9dhEsTe9Q3uLy/exnDrZM+4z8pH9ytz55Xdo++i0KBMP3PuBTjzW76dDIYKcgWazGV9klOe9Q2tvfBqdPuRAKA/Zr5o+XLmPTMlx4Nl2O5uGIR/4vfhqfC+MZFCSkvmD6Urmg1nmBLkcJ+uXE3n30cw3pLN3giCUf/yOKvMn3u7NfB7LHPkwc1/q8IQoa8g+OoQ+9hY+PDuf0okQphNv005kJzLddB4X73CqVZWcD80aRUe0qDEY0bpG9Y5oCQR9NmpNGdE2pmmn6U+njO6+JxjaVHeE5toxkuaKqoJcXx/ZmyuBIFdUl5Lr/nTNOPpelZF9xyi3eXoqOfAWHYpgsZRxdAUaxA/30fprQqIcFNd9o178n7L4KKASfxfW6S0sPn5OJA99m5rytSwseJuuf4wgpk1Nyx3NxITwkk6/5rHZ1zyjydfvU5Td1oeyw4oZsYzw8gIz2p3iKR7vw1O0m/RNNPgmmTXtH66ysfeHX5yNfSuXcnyvQW3/51tcbde8qZo1Xb6Xvrm4DfvKEjJrciU7bDptKsDouEJD5k0lZN400BOdiStlae7EPARh2uRi0yYXmzZBoYutZHJbnZzc3pY6ubW13pDSOVzSR+dwHnKJ32dQC/E3SC0sGqZqc7cPu8g2921qoeYNgzYz8k2uzXS9oaqFH+75xlr4n73fshYGmpRaMJt0auFoSnv7i3F7iz8hMK96t0BnPwtfT05fT8of7CEPCiHRszh9xTwP4pU2z9+k5Lm2jzbeoKfuM6/T5Y3XXyMvojyFM9fGRU6h+1o97pcY9y8pt3qei75r/x79zmUDi1gLEeO2s+R96qIlZWLL8Rx39Lw7tjwXxwkTyTjhqpQn/79hr5xe8xpOr+fStyxiy3P6ivMTFuf0qyRODouT3VecVhbnBRqHDrpjozDKWBJlRHK2attDnfVPCGsGfR7+Ys7tRct3qIx/cW9teOxpMfjX7VYx3MIzDASGgd0uFcMCnmEoMAztns0NN4+QJ4gFdnkSqnaf+unhWXJTsltlG949rr47OEHvZsufQCniZiD58Xvv/LEU6qgkdiMxySfJGs7CHFvbY0Q7o8kbYIXd0qqi51GR3TNV0l+SWn6u2V9NJA9D7t0jNrD3pcaS96VGKE99PIUfRf4bn6pM2p3yqtSrkD1WjhVrYtBuamLpu/kasXKjbc37C4vRAO87vpYMcM6TKV0OGix+gZR8w/1qkE0s/BkBpYEwgkd2qOVlO8T2O+xWMpxDvptAv1texWHkBIac202mgXQIjJZD3qfGhe01adaYlDYel7QfxKLnIPvy3fRhsZWtY28BuqPVvhqyu5riIBpSuO2PIP9itzLIPbqbPhmhE+JZdrka0nT+yYSqxWHEj1+BmfuJLfj17mbc+gQxx6t0bBpLXzE0V2Cveg8KD1X8vCfNis+ksqmHn2NfeqHufY2J+BsMUtx7Ey46fu8V+rgrm/r2NXZRnvMqLXmF3H83bVRjqXjdy4iM6qnJt8q9H+TubIUJlzlBx1i7XsFHKeeJPyoTo2eTo/XvWuWvyTcdh2+P/+gV3ft/o/dl6RXGF3sJG1DSvrT8v2P8cxT+2/vmX8P4hyr8E5E/yb6hVP4N3JEjL7P1Hmiu0UTREnf0dNFid/TtonJP+1Vdg3KFxWL7JBnCMs+EozCn337Ogl/sya5ddEVkVO/7wcc80dNzII3E0L9BEzNBq44cI21omdKIdnDyfraDffvHPvUzqb6q1tkfrdq/anJYqq5rEHL7C/wWFdddF45UwaUGxG0kgg1ARXxSbkMkEMhtCEq5qyoDddVCXQMJcwN1kj9UGcitCYZyA8GGFeMn5K6uk2pzcfeFXEf+dVcL7skLc4ONwITbLuTC/2R/g+rcmrqAXwhNFOZCmDsGWRpIKrjBDWQvFAcjgeqGqyV2B7nU5VngmOKd51k4u8jj9S7wOmY2Nku1wYY63zTcSyLsyF9SGYj4XbjTiOtC+KeWSZUN1bjdB4vSN3+hS9lKwnVh8kydDSrhI2Wz7+q7bnGqvtdPfl/M7j/F7mcvcureX8vu5xvcL2X3SzX3+5Z3hnshp7sLKN90V8OqulCwod7fIGliquXZtkhfHuX+BgUvc+rvp8ju45iHfPfMQu1+U8nvrsvU/I3fwN+oSX+jht803HL9Gvbt/qYXEwl8b6kWGnMTNL8ohLjY3gSuAl8YHI9vbkG46zTgENb2JBL4HqD4JThNCJfCUCwH4uF3VfkQPonfV0G4H0JcWs4BH7QBwgch3M+at/KNvumuRYKpKds0fGCmdYMpM3so+/493plI8N9t6/PTb83JmsuOROIp7Nezsudm5dxsG7Daula4adj110y1j+X3BbXcVeohKWRacAssi5JOAftuvQLK/ltoo2nPL3EKRVnZs7NyZmflzs4aPzsrvyhr5rysjektmesy2tPXp/3A8oCZxLsDv3eWE4mfD4R4G5bqx9uWpYo3NCmPujwjmKzjv0gkHsZOenZWdlFWzpys/BbLejOVE/fBeBLq4g2ycV1KXkVZTlVW5IdlS4P0Ss8kEoNwB5Da7yhyFmXlQrEsLWnrgRvl+hl+yw11O5Kl32Km+sevkpyAX6XB8YHsUh38CNqhDv411tfORGIMw5V9TY+AfGuB3y/Qcv/A7MrKWW9xZeW2p7myxq9LF7PyH8gQs2a2ZJZkOQNYUijveFJ20ACUxUrSvxZtENLR9iQJyx6LpdOC397i9827cbnsTkYcQQLfc8UvlZ34uXHERHeYOI93XGbK9gV+CH0bI84hEQQiuR9uo4XG+RPebrHQLTM2X8r2b8OPsI+ggK3pNIFL8M9rjBiPfwZn0DhOIEzT2Z54IhLrMihbKf75JRDTlUzfyaTN+J3BwNaTSSU4jF+AD+pHNxeZisi9A+hOIL/DJNcPoHem4Z1SsFv8YHEI3ukCYkVyt7tBlO0wSv2hTRC8uO0DUQjUWqmyQcmPL6ObBdyHd664nMYhbKPgzwSlHuZdQcvzPfw6fO0VdAOMY0hshT+zlG1Tzo6ggj6E9pc3isZZk8vqZaVZtcNvwvLmfYJlDyEOKGIfYJUaxM/6+5nojin/ielLjDiHxK9NdC8PM7J9ZqJxbEjgd7BWRZ5sVnVOLO7YdLo/xM1ILEjnNvFQdkSdjXd+wdi2IfEKEH9WUru/Hy0dfjooWFmdbMT9AIbAn5ip11YFywKyU6+SAV404i0ktvP7orzJNn95DGMfZjt8/KeJ8WaZhH/9/vX71+9fP+Nf9kg2/mb7uJ8aoR5XmgzCfelquktDn2O0sqfU0hyarrKXVHkppZW9k5R9xJU9k5S9ooYp+ySx+8p4TtkLC6bfQbJvjtmZ3M+LpNfPmdzPjA64KK3sifU6u6HshaXs7XSpRj+W3g202H5yrMdPV49Ple3glb2j5CFOFd412KmS28oU1U+T//kELY+T8ScYrchxitFPZjv/T+0kuY+95vcIq9cnWPgsCztYuI+FH7LwNAsz2D63l7FwHAuns3AuC5ewsIaFq1j4AAsfYeETLHyWhR0s3MfCD1l4moUZbD50GQvHsXA6C+eycAkLa1i4ioUPsPARFj7BwmdZ2MHCfSz8kIWnWZjB9uG9jIXjWDidhXNZuISFNSxcxcIHWPgIC59g4bMs7GDhPhZ+yMLTLMxg7fwyFo4boW9P84qLr8sdv7gq0iBFcgvyZuYVTJoSIZTjHkdBXn5BXsEEiguMyReobFiRu8ofCuOSydS8aXn5kwpolCn3SKFIWGqekjteqlwRnrzI5XEVlbm8U6flT67BbTIn5I7HtZdqXGnxeJaU0OgTYDgYbq6XKqsglEI0rFWu6hokf6hRyGsISv68otnuSZA0o1Y0RPKqInWB6kl11QKhaivDtUJedXMDpEdDKUTvMIFVhBfuhfyBSmRkV40BCbOsg7+Svwn+gtx1cC9YXSlVCnn+Wm9NqLLe762tDvVSkKjPx7Yo9UpkO2SShrcyFKpspmko13f6QkSwyvo6H8QLSuQPzZfmURUOC3m+YD2uVXzrdj2c+WzFr/WeryGo/K22P1B+V2r2ROw9v4KtX2j40zS0QxNfYvElbv7aV3ycP8KUOKjEV/qBRxlQzfB0Tb+RXBdifYBZ008oDnc/6ycyWNmtGn+9hLGaNf3O/n7qfsZIf8uZj1fiK379SdYBPqSRX3OMiLCS9RkKrfQbTrapovLOZgaTU1v+u5hOzZp+qmuwup/S6k8pf6smvtLvyUPU/WQ6Gwto468Xes9c4ccJS3PU/b9R/Uc18dey+GtZ/KcsmvGOJnxYE18ZB+Uzwx9boB9f+f1UE18Z15SXqvt3I/k3atpfBYtfweLXWvrO/0lN/N5zYCi95hvyf1YTXyx3slBQtUPBoP1s08TH5TMaagdQ+vnvZWuRFs04UDlnRltebf748p+Ni6+ME+Vl+vxa+hiTPzm+YvFPXWD8k1zb4sdJyjlAimIyNPGVcvVo8lf24e3x9p2/Ep7TxFfGqQILZFPf8XFHAT6+zPZplCsvTP8D2cJKMn+2n28Pi2/V1L+2PxjM8s/XjjdZ/AcM+h8lHJxqYuR3TxXzH6a+/S9vu/xv6UrmD9hmtrgyOF/Hf/UzyP/Bu2hoG9x3/n39LMCt9Mdq3JzsZ9W4Jdl/qvG0ZL+oxtN7+zsVnpHsx9R4pu68wwJaUfodNd4v2Z+o8f7JfkKND0j6fzU+MOnX1figpL9W41lJP6zGbUn/qsazk35TjQ9O+kM1PiTp59T4JUn/pcaHJv2SGr806W/U+GW68y0LzC4V/6DGc3rbvQq/Itme1XjvuSdqfHgKZiI++5OEFqd75abq4UaG4+MQ/lfKcHz8wP+qSPvrrccx3LjEBHKma85P+TXjV55rXcUt/SLu1OC4CIq48jxM2Ut5NsM33Ezxh1kGAYY3atL5d4bneyj+BsNPMPzUDRT/OVvweMhM8ewStu7BnMxfzbRcaZpy7Sa4Lfn8TvEvXzM8W4NPtlC8VINXMVx5/qjgjzI8V4O/yPB8TTqfKumz56/K3shj0yiuPPdV9jpezPC1GvxBhivPTZW9i7cwXHleOl7pjxmuPDdWngXmpFN8Y5maX2S4U4N/l+GNGvy/0vXt+RnCn9oet6bTelyr8TNvMfwpDf4Rw7XraOfSab2bNPU+MAOvU/3D1AxmPyPV6dxE+FP9jFG5lhP+wcImTTsNZOiXVzBo702EP9XPrCcDm0tS5P8Fw7VyPkPSSfVvf8nAsUGqv+owOB/qqAE+OFMfv4rgg4RS5v+VPn8aw2/R1NesTP3zob5rkP5GA3xXpv65Y+8Y4N0G6SQM8BFWfbyE4Kn9YJkBf5MBvs4A/4UBvsUAP2aAD+hnUF8G+AIDvBnwseZBwh7mt5V13Q399M/betMgnQ/76Z/DNaC/fn1d3R/HoL3jCmV+M72/fvqLDfAVBvjDBviTBvK80B/H7Knt6HWDdM721z/vLHeAPr97gP55ZMEB+ueyPYT85iuEHo08jxmkv2WA/rlmbxvwf8rSP6VJP2HAf8lA2t67mJ34lXWsgfr8aw3wHw/UP2/uDwb8bw9EnmEpenjfgP/rgfrn1jkG6fPfYoCvMsB/YoBvGqRvV68O0j//7jODdDKz9PHhBni1Ab7KAF+fRfVp9av1+SMD/v0G+PEs/fPycNNnPX6PTf+8v+8a8P+7jbZHbb1vtOmfx7fdIJ3Ls/XxawzwuQb4cgN8Tbb+eYWPGPD/3gDfa4AfNcDTBtP26GTjnN8yhfYjuM58cHIoGJQmNzZXSr5gtT80uTEUrAr468OTK6t8joIZk4sn4wFTeb7GRnK+FL/onp+COFKQaULyNcFwpMrr9iZT895m9A6hw+H14mMGqa7B6/UULAg20LPeLvgVzzn59DCvi3kH8x+KM+UC4hTg26oXxKm8ZflNokSkugCUN1xbGfJXe0P+GneZNH2V3ycFQ+4FZflemho5666s0l02zetyuRQB5l+IzonIM2oiDZjkTHwHN1DX4PcF3Dcv6k2fMLkw6XJfIBzqIyVXMolwI7KCZNWuGTXB0OrKULW73OuqaSQiNi4sK/T2JWRvwXyrAuwwSM9Mr7cuSJ4g4cGCF/Me8AXwa9/TvZAomleHLyCKztuy3xyr953cb+YtVBeh7CK1VHbxWiq7eC2V/UNaKrsILZVdlJaWXKSWlly8lpZcqPC+kBSWIjU1eT7B6725eJHX4y4r93qF3mNjvVK914fHw4YFHcjrrQ56VwSCVZUBbzU06rC3MtIk+IL1jQG/5K/Om144c4o+k7f3YaoXFB9qFugD2epIfX0zROEob+8zWMbq9c5dVFTi8roWzMHDb4nk7JqVeuHcuWWucm950WyPCzlUSVSrAXLeoeCd850FRSXuYgGf3iqY9kROp5M/xbDvE0zVvPQYRoaxkxPZeYu+cIRoQ0jmepEHfGql0j37NkV03dN5VVx5hRd0zjA5yzI1ee7ETB219XEAsFoGh0Ng2tE/dVOjZnKipVrN5NBMXc33nnSpud3nMafa0qQcGKph4E7jTM3G4HDe1Co1PEg3JTd8scOLJ4J6k8cO/2PHDKtTJieN6hQg9RhijUR9nkO90Eu+FvJGwv7q1OOHNRKE/P4UAfo6JFgdnZ6Oqkmgj4OwtY7A8KxrPfNOOQVW13XoHWWt05J0DqrVcumcfaw1DCie4iVTTn5OtTdyYHAqzB1lrU2/Ohz01kLvC8qjJ9Qaejs2rPonHrmt9VvsSFuttaiPjNaWLvWwZW0Rq8JhziKS542nVMYFHULsdHJH56YenazrRVLOUU5NRH3WtF4q6oPc1SnoHv9ucGp6Sg/nq29Ua9yn446/xYniGnfgD9ZoTSx57rq6VKTP/8dO9dbkST4sTDGrCz5UW6er1jnp3sgFGBxYrlfH3InnGlWQt9P0jipPNaV/wpHcOp2lTulYr5fi/FTnYMM9dhK19pj7VK0qJ5brjHromeM6QmgPZE8178bm3pp3FKSe660di9Q1CNTX/S/GaLOal4sAAA=='
bin = gzip.decompress(base64.b64decode(gz))
p = os.path.dirname(__file__)
pymain = os.path.join(p, "a.out")
with open(pymain, "wb") as f:
    f.write(bin)
os.chmod(pymain, stat.S_IRUSR | stat.S_IWUSR | stat.S_IXUSR)
if p == "":
    pymain = "./" + pymain
subprocess.call(pymain)


# compiled by pythran
'''
#pythran export main2()
import numpy as np
i8 = np.int64
i4 = np.int32


def solve(a, b, N):
    ans = 0
    nmax = 2 ** N - 1
    for n in range(nmax, 0, -1):
        d = n
        count = 0
        for i in range(N - 1, -1, -1):
            if d & 1:
                count += 1
                if n & a[i] > 0 or n | b[i] < nmax:
                    break
            d >>= 1
        else:
            ans = max(ans, count)
    return ans


def main2():
    stdin = open('/dev/stdin')
    N = int(stdin.readline())
    x = np.empty((N, N), i8)
    x.fill(-1)
    for i in range(N):
        A = int(stdin.readline())
        for _ in range(A):
            a, y = map(int, stdin.readline().split())
            x[i, a - 1] = y
    a = np.zeros(N, i8)
    b = np.zeros(N, i8)
    for i in range(N):
        for j in range(N):
            a[i] <<= 1
            b[i] <<= 1
            if x[i, j] == 0:
                a[i] += 1
                b[i] += 1
            elif x[i, j] == -1:
                b[i] += 1
    ans = solve(a, b, N)
    print(ans)
'''

Submission status: Accepted

Solution code:
import numpy as np
i8 = np.int64
i4 = np.int32


def solve(a, b, N):
    ans = 0
    nmax = 2 ** N - 1
    for n in range(nmax, 0, -1):
        d = n
        count = 0
        for i in range(N - 1, -1, -1):
            if d & 1:
                count += 1
                if n & a[i] > 0 or n | b[i] < nmax:
                    break
            d >>= 1
        else:
            ans = max(ans, count)
    return ans


def main2():
    stdin = open('/dev/stdin')
    N = int(stdin.readline())
    x = np.empty((N, N), i8)
    x.fill(-1)
    for i in range(N):
        A = int(stdin.readline())
        for _ in range(A):
            a, y = map(int, stdin.readline().split())
            x[i, a - 1] = y
    a = np.zeros(N, i8)
    b = np.zeros(N, i8)
    for i in range(N):
        for j in range(N):
            a[i] <<= 1
            b[i] <<= 1
            if x[i, j] == 0:
                a[i] += 1
                b[i] += 1
            elif x[i, j] == -1:
                b[i] += 1
    ans = solve(a, b, N)
    print(ans)


main2()

Submission status: Accepted

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    XY = [[] for _ in range(n)]

    try:
        it = iter(args[1:])
        a = next(it)
        i = 0
        while a:
            for _ in range(int(a)):
                x, y = map(int, next(it).split())
                XY[i].append((x-1, y == 1))
            a = next(it)
            i += 1
    except StopIteration:
        pass

    ret = 0
    for hypo in range(2**n):
        consistent = True
        truth = [None]*n
        count = 0
        i = 0
        while consistent and i < n:
            if (hypo >> i) & 1:
                count += 1
                for x, y in XY[i]:
                    if truth[x] is None:
                        truth[x] = y
                    elif truth[x] != y:
                        consistent = False

                    consistent &= (hypo >> x) & 1 == y
            i += 1

        if consistent:
            ret = max(ret, count)

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

Solution code:
n = int(input())
a = []
x = [[] for i in range(n)]
y = [[] for i in range(n)]
for i in range(n):
    a.append(int(input()))
    for j in range(a[i]):
        xx, yy = (int(i) for i in input().split())
        x[i].append(xx)
        y[i].append(yy)

testimony = [[2]*n for i in range(n)]

for i in range(n):
    for j in range(a[i]):
        if(y[i][j] == 1):
            testimony[i][x[i][j]-1] = 1
        elif(y[i][j] == 0):
            testimony[i][x[i][j]-1] = 0

ans = 0
for i in range(2**n):
    bit_list = []
    for j in range(n):
        if ((i >> j) & 1):
            bit_list.append(1)
        else:
            bit_list.append(0)
    flag = 1
    for k in range(n):
        if(bit_list[k] == 1):
            for l in range(n):
                if(testimony[k][l] != 2):
                    if(testimony[k][l] != bit_list[l]):
                        flag = 0
                        break
    if(flag == 1):
        ans = max(sum(bit_list), ans)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = []
x = [[] for i in range(n)]
y = [[] for i in range(n)]
for i in range(n):
    a.append(int(input()))
    for j in range(a[i]):
        xx, yy = (int(i) for i in input().split())
        x[i].append(xx)
        y[i].append(yy)

hoge = [[2]*n for i in range(n)]

for i in range(n):
    for j in range(a[i]):
        if(y[i][j] == 1):
            hoge[i][x[i][j]-1] = 1
        elif(y[i][j] == 0):
            hoge[i][x[i][j]-1] = 0

ans = 0
for i in range(2**n):
    bit_list = []
    for j in range(n):
        if ((i >> j) & 1):
            bit_list.append(1)
        else:
            bit_list.append(0)
    flag = 1
    for k in range(n):
        if(bit_list[k] == 1):
            tmp = 0
            for l in range(n):
                if(hoge[k][l] != 2):
                    if(hoge[k][l] != bit_list[l]):
                        flag = 0
                        break
    if(flag == 1):
        tmp = 0
        for l in range(n):
            if(bit_list[l] == 1):
                tmp += 1
        if(tmp > ans):
            ans = tmp
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = []
x = [[] for i in range(n)]
y = [[] for i in range(n)]
for i in range(n):
    a.append(int(input()))
    for j in range(a[i]):
        xx, yy = (int(i) for i in input().split())
        x[i].append(xx)
        y[i].append(yy)

hoge = [[2]*n for i in range(n)]

for i in range(n):
    for j in range(a[i]):
        if(y[i][j] == 1):
            hoge[i][x[i][j]-1] = 1
        elif(y[i][j] == 0):
            hoge[i][x[i][j]-1] = 0

ans = 0
b_list = []
for i in range(2**n):
    bit_list = []
    for j in range(n):
        if ((i >> j) & 1):
            bit_list.append(1)
        else:
            bit_list.append(0)
    b_list.append(bit_list)
    flag = 1
    for k in range(n):
        if(bit_list[k] == 1):
            tmp = 0
            for l in range(n):
                if(hoge[k][l] != 2):
                    if(hoge[k][l] != bit_list[l]):
                        flag = 0
                        break
    if(flag == 1):
        tmp = 0
        for l in range(n):
            if(bit_list[l] == 1):
                tmp += 1
        if(tmp > ans):
            ans = tmp
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    T = [[None]*n for _ in range(n)]

    try:
        it = iter(args[1:])
        a = next(it)
        i = 1
        while a:
            for _ in range(int(a)):
                x, y = map(int, next(it).split())
                T[i-1][x-1] = y == 1
            a = next(it)
            i += 1
    except StopIteration:
        pass

    ret = 0
    for hypo in range(2**n):
        consistent = True
        truth = [None]*n
        count = 0
        i = 0
        while consistent and i < n:
            if (hypo >> i) & 1:
                count += 1
                j = 0
                while consistent and j < n:
                    t = T[i][j]
                    if t is not None:
                        if truth[j] is None:
                            truth[j] = t
                        elif truth[j] != t:
                            consistent = False

                        consistent = (hypo >> j) & 1 == t
                    j += 1
            i += 1

        if consistent:
            ret = max(ret, count)

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    X = []
    for i in range(N):
        a = int(input())
        X.append([])
        for j in range(a):
            x, y = [int(x) for x in input().split()]
            X[i].append([x, y])

    ans = 0
    for i in range(2 ** N):
        tmp = 0
        is_mujun = False
        for j in range(N):
            if i >> j & 1:
                tmp += 1
                for k in X[j]:
                    if (i >> (k[0] - 1) & 1) != k[1]:
                        is_mujun = True
                        break
        if not is_mujun:
            ans = max(ans, tmp)

    print(ans)







if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = [0] * n
s = [[]] * n

for i in range(n):
  a[i] = int(input())
  tmp = [[]] * a[i]
  for j in range(a[i]):
    tmp[j] = [num for num in map(int, input().split())]
  s[i] = tmp
# print(n)
# print(a)
# print(s)
ans = 0
for i in range(2 ** n):
  pattern = '{:0' + str(n) + 'b}'
  bin_str = pattern.format(i)
  # print(bin_str)
  all_ok = True # すべての人の証言に矛盾がない
  total_honesty = 0
  for j in range(n):
    shogen = s[j]
    if bin_str[j] == '1':
      total_honesty += 1
      # 正直者とした場合
      for k in range(len(shogen)):
        x, y = shogen[k]
        x -= 1
        if int(bin_str[x]) != y:
          all_ok = False
          break
  if all_ok:
    if ans < total_honesty:
      ans = total_honesty
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    axy = [[[],[]] for _ in range(n)]
    for i in range(n):
        a = II()
        for _ in range(a):
            x, y = LI()
            axy[i][y].append(x-1)
    ans = 0
    for i in range(1 << n):
        f = 0
        tmp = 0
        for k in range(n):
            if i & (1 << k):
                tmp += 1
                for x in axy[k][0]:
                    if i & (1 << x):
                        f = 1
                for x in axy[k][1]:
                    if not(i & (1 << x)):
                        f = 1
        if f:
            continue
        ans = max(ans, tmp)
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n = int(input())
info = [[] for i in range(n)]
for i in range(n):
    a = int(input())
    info[i] = [tuple(map(int, input().split())) for _ in range(a)]

ans = 0
for bit in range(1 << n):
    flag = True
    cnt = 0
    for i in range(n):
        if (bit >> i) & 1:
            cnt += 1
        else:
            continue

        for x, y in info[i]:
            b = (bit >> (x - 1)) & 1
            if b != y:
                flag = False
                break
        if not flag:
            break
    if flag:
        ans = max(ans, cnt)

print(ans)