The PDF version of this problem can be downloaded here.



Tomato the Great own a pizza factory, which produces pizzas from an assembly line. That is, each worker in your factory only does one single step of pizza production. One worker makes dough; another put toppings on the dough; yet another put cheeses on the dough; and someone else send the dough into the oven.

The Pizza Festival is coming, and Tomato the Great would like to prepare a great pizza for the great event. He would like the pizza consists of as many ingredients as possible. But he knows that some of the ingredients conflict with each other, and that putting those conflicting ingredients together results in a terrible pizza.

After carefully investigating, Tomato the Great finds out 31 key features of the ingredients. For example, the pineapple is sour and sweet, and the sausage is salty and contains meats. He uses binary string si of length 31 to describe each ingredient i. Each digit in the string represents a key feature. The j-th digit in the i-th binary
string is 1 if the i-th ingredient has the j-th feature, or 0 otherwise. Moreover, Tomato
the Great finds out the key of conflict: Two ingredients conflict with each other if and
only if their binary strings dier at only 1 digit.

Now, Tomato the Great would like you to gure out a set of ingredients without any conflict, and the size of the set should be as large as possible. Then, he will prepare the
great pizza with these ingredients. What is the maximum number of ingredients that he can use?
Warn: 本題有 specialjudge