ZOO - Zoo

题面翻译

新建的圆形动物园是亚太地区的骄傲。圆形动物园坐落于太平洋的一个小岛上，包含一大圈围栏，每个围栏里有一 种动物。如下图所示：

你是动物园的公共主管。你要做的是，让每个来动物园的人都尽可能高兴。今天有一群小朋友来动物园参观，你希望能让他们在动物园度过一段美好的时光。但这并不是一件容易的事——有的动物有一些小朋友喜欢，有的动物有一些小朋友害怕。如，Alex 喜欢可爱的猴子和考拉，而害怕拥牙齿锋利的狮子。而Polly 会因狮子有美丽的鬃毛而喜欢它，但害怕有臭味的考拉。你可以选择将一些动物从围栏中移走以使得小朋友不会害怕。但你不能移走所有的动物，否则小朋友们就没有动物可看了。每个小朋友站在大围栏圈的外面，可以看到连续的 $5$ 个围栏。你得到了所有小朋友喜欢和害怕的动物信息。当下面两处情况之一发生时，小朋友就会高兴：

• 至少有一个他害怕的动物被移走
• 至少有一个他喜欢的动物没被移走

例如，考虑下图中的小朋友和动物：

• 假如你将围栏 $4$ 和 $12$ 的动物移走。Alex 和 Ka-Shu 将很高兴，因为至少有一个他们害怕的动物被移走了。这也会使 Chaitanya 高兴，因为他喜欢的围栏 $6$ 和 $8$ 中的动物都保留了。但是，Polly 和 Hwan 将不高兴，因为他们看不到任何他们喜欢的动物，而他们害怕的动物都还在。这种安排方式使得三个小朋友高兴。
• 现在，换一种方法，如果你将围栏 $4$ 和 $6$ 中的动物移走，Alex 和 Polly 将很高兴，因为他们害怕的动物被移走了。Chaitanya 也会高兴，虽然他喜欢的动物 $6$ 被移走了，他仍可以看到围栏 $8$ 里面他喜欢的动物。同样的 Hwan 也会因可以看到自己喜欢的动物 $12$ 而高兴。唯一不高兴的只有 Ka-Shu。
• 如果你只移走围栏 $13$ 中的动物，Ka-Shu 将高兴，因为有一个他害怕的动物被移走了，Alex, Polly, Chaitanya 和 Hwan 也会高兴，因为他们都可以看到至少一个他们喜欢的动物。所以有 $5$ 个小朋友会高兴。这种方法使得了最多的小朋友高兴。</div>

输入格式

本题有多组数据。

第一行包含一个整数$T$，表示数据组数。

对于每组数据，输入的第一行包含两个整数 $N$，$C$，用空格分隔。

$N$ 是围栏数（$10 \le N \le 10^4$），$C$ 是小朋友的个数（$1 \le C \le 5\times 10^4$）。

围栏按照顺时针的方向编号为 $1,2,3,\cdots,N$。

接下来的 $C$ 行，每行描述一个小朋友的信息，以下面的形式给出： $E, F, L ,X_1, X_2 ,\cdots ,X_F ,Y_1 ,Y2 ,\cdots ,Y_L$。

其中： $E$ 表示这个小朋友可以看到的第一个围栏的编号（$1 \le E \le N$），换句话说，该小朋友可以看到的围栏为 $E$， $E+1$， $E+2$， $E+3$， $E+4$。

注意，如果编号超过 $N$ 将继续从 $1$ 开始算。

如：当 $N=14$，$E=13$ 时，这个小朋友可以看到的围栏为 $13,14,1, 2$ 和 $3$。

$F$ 表示该小朋友害怕的动物数。

$L$ 表示该小朋友喜欢的动物数。

围栏 $X_1, X_2, \cdots, X_F$ 中包含该小朋友害怕的动物。

围栏 $Y1, Y2, \cdots, Y_L$ 中包含该小朋友喜欢的动物。

$X_1, X_2, \cdots, X_F, Y_1, Y_2, \cdots, Y_L$ 是两两不同的整数，而且所表示的围栏都是该小朋友可以看到的。

小朋友已经按照他们可以看到的第一个围栏的编号从小到大的顺序排好了（这样最小的 $E$ 对应的小朋友排在第一个，最大的 $E$ 对应的小朋友排在最后一个）。

注意可能有多于一个小朋友对应的 $E$ 是相同的。

输出格式

对于每组数据，输出一个数，表示最多可以让多少个小朋友高兴。

题目描述

The pride of the Asia-Pacific region is the newly constructed Great Circular Zoo. Situated on a small Pacific island, it consists of a large circle of different enclosures, each containing its own exotic animal as illustrated below.

You are in charge of public relations for the zoo, which means it is your job to keep people as happy as possible. A busload of schoolchildren has just arrived, and you are eager to please them. However, this is no easy task|there are animals that some children love, and there are animals that some children fear. For example, little Alex loves monkeys and koalas because they are cute, but fears lions because of their sharp teeth. On the other hand, Polly loves lions because of their beautiful manes, but fears koalas because they are extremely smelly.

You have the option of removing some animals from their enclosures, so that children are not afraid. However, you are worried that if you remove too many animals then this will leave the children with nothing to look at. Your task is to decide which animals to remove so that as many children can be made happy as possible.

Each child is standing outside the circle, where they can see five consecutive enclosures. You have obtained a list of which animals each child fears, and which animals each child loves. A child will be made happy if either at least one animal they fear is removed from their field of vision, or at least one animal they love is not removed from their field of vision.

For example, consider the list of children and animals illustrated below:

```

---

|Child |Enclosures Visible |Fears |Loves | |Alex |2, 3, 4, 5, 6 |Enclosure 4 |Enclosures 2, 6| |Polly |3, 4, 5, 6, 7 |Enclosure 6 |Enclosure 4 | |Chaitanya |6, 7, 8, 9, 10 |Enclosure 9 |Enclosures 6, 8| |Hwan |8, 9, 10, 11, 12 |Enclosure 9 |Enclosure 12 | |Ka-Shu |12, 13, 14, 1, 2 |Enclosures 12, 13, 2 |- |

Suppose you remove the animals from enclosures 4 and 12. This will make Alex and Ka-Shu happy, because at least one animal that they fear has gone. This will also keep Chaitanya happy, since both enclosures 6 and 8 still contain animals that he loves. However, both Polly and Hwan will be unhappy, since they cannot see any animals that they love but they can still see all the animals that they fear. This arrangement therefore gives a total of three happy children.

Now suppose you put these animals back into their enclosures, and remove the animals from enclosures 4 and 6 instead. Alex and Polly will be happy because the animals that they fear in enclosures 4 and 6 have gone. Chaitanya will be happy because, even though animal 6 has gone, he can still see the animal in enclosure 8 which he loves. Likewise, Hwan will be happy because she can now see the animal in enclosure 12, which she loves. The only person unhappy will be Ka-Shu.

Finally, suppose you put the animals back once more and then remove only the animal from enclosure 13. Ka-Shu will now be happy since one animal that he fears has been removed, and Alex, Polly, Chaitanya and Hwan will all be happy since they can all see at least one animal that they love. Thus this arrangement gives five happy children, the largest number possible.

## 输入格式

Multiple test cases, the number of them will be given at the very first line.

For each test case:

The first line will be of the form N C, where N is the number of animal enclosures (10 <= N <= 10 000) and C is the number of children (1 <= C <= 50 000). The enclosures are numbered 1, 2, ...,N clockwise around the circle.

Following this will be C additional lines of input, where each line describes a single child. Each of these lines will be of the form:

 `E F L X1 X2 ... XF Y1 Y2 ... YL;`where:

- E is the first enclosure that the child can see (1 <= E <= N). In other words, the child can see enclosures E, E + 1, E + 2, E + 3 and E + 4. Note that numbers larger than N wrap back around the circle, so if N = 14 and E = 13 then the child can see enclosures 13, 14, 1, 2 and 3.
- F is the number of animals that the child fears, and L is the number of animals that the child loves.
- Enclosures X1,...,XF contain the animals that the child fears (1<=X1,...,XF<=N).
- Enclosures Y1,...,YL contain the animals that the child loves (1<=Y1,...,YL<=N).
- No two of the integers X1,...,XF,Y1,...,YL are equal, and all of these integers describe enclosures that the child can see.

## 输出格式

Output must consist of a single integer, giving the largest number of children that can be made happy.

## 样例 #1

### 样例输入 #1

2 14 5 2 1 2 4 2 6 3 1 1 6 4 6 1 2 9 6 8 8 1 1 9 12 12 3 0 12 13 2 12 7 1 1 1 1 5 5 1 1 5 7 5 0 3 5 7 9 7 1 1 7 9 9 1 1 9 11 9 3 0 9 11 1 11 1 1 11 1

### 样例输出 #1

5 6

Explanation: The first sample case is the example discussed earlier, in which all C = 5 children can be made happy. The second sample case is an example in which it is impossible to make all C = 7 children happy.