Helping Hiasat
Contest: Codeforces Round 533 (Div. 2)
Difficulty rating: 2200
Tags: bitmasks, brute force, dp, meet-in-the-middle

Hiasat registered a new account in NeckoForces and when his friends found out about that, each one of them asked to use his name as Hiasat's handle.

Luckily for Hiasat, he can change his handle in some points in time. Also he knows the exact moments friends will visit his profile page. Formally, you are given a sequence of events of two types:

- $$$1$$$ — Hiasat can change his handle.
- $$$2$$$ $$$s$$$ — friend $$$s$$$ visits Hiasat's profile.

The friend $$$s$$$ will be happy, if each time he visits Hiasat's profile his handle would be $$$s$$$.

Hiasat asks you to help him, find the maximum possible number of happy friends he can get.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^5, 1 \le m \le 40$$$) — the number of events and the number of friends.

Then $$$n$$$ lines follow, each denoting an event of one of two types:

- $$$1$$$ — Hiasat can change his handle.
- $$$2$$$ $$$s$$$ — friend $$$s$$$ ($$$1 \le |s| \le 40$$$) visits Hiasat's profile.

It's guaranteed, that each friend's name consists only of lowercase Latin letters.

It's guaranteed, that the first event is always of the first type and each friend will visit Hiasat's profile at least once.

Output format:
Print a single integer — the maximum number of happy friends.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, the best way is to change the handle to the "motarack" in the first event and to the "light" in the fourth event. This way, "motarack" and "light" will be happy, but "mike" will not.

In the second example, you can choose either "alice", "bob" or "tanyaromanova" and only that friend will be happy.

Example input:
5 3
1
2 motarack
2 mike
1
2 light

Example output:
2

Example input:
4 3
1
2 alice
2 bob
2 tanyaromanova

Example output:
1

Editorial:
Let's change this problem to a graph problem first.
Let's say, that each action of the first type is a "border". Consider all friends visiting our profile after this "border" but before the next one. Clearly, we can satisfy at most one of them. Let's change the friends into graph nodes and add edges between every two friends that are between the same borders.
Then it's enough to solve "the maximum independent set of the graph", clearly any possible answer must be an independent set and by any independent set we can always build a way to change our handle.
The maximum independent set can be solved in $$$O(2^m)$$$ (where $$$m$$$ is the number of friends). But since $$$m$$$ is up to $$$40$$$, it is too slow. However, we can apply the meet in the middle approach and then it becomes $$$O(2^{(m/2)})$$$ or $$$O(2^{(m/2)} m)$$$.
The simplest way is to do the following (notice, that the independent set is same as clique if all edges are inverted, so we will solve a max clique problem).
Let's write a bruteforce solve(mask) which returns size of the largest clique, which forms a subset of mask. The answer will be just to run solve of full mask.
How to write solve? Let's find a first bit of mask, let it be vertex $$$v$$$.
There are two cases:
1. The vertex $$$v$$$ is not in an answer. Kick it and run a recursive call.
2. The vertex $$$v$$$ is in answer. Hence all other vertices of answers are neighbors of $$$v$$$. Run the recursive call from mask & g[v], where g[v] denotes the mask of neighbors.
Clearly, it works in $$$O(2^m)$$$. However, if we add memorization (don't calculate for same mask twice) it is magically becomes $$$O(2^{m/2})$$$.
Why? Consider the recursion, there are at most $$$m/2$$$ recursion calls before we arrive into the state, where there are no set bits of the first half.
This part will take at most $$$2^{m/2}$$$ then. And clearly there are at most $$$2^{m/2}$$$ states with no set bits in the first half.