406388: GYM102394 E Exchanging Gifts

After the dress rehearsal of CCPC Harbin Site 2019, $$$m$$$ contestants are still in the contest arena. They are taking photos, discussing the problems, and exchanging gifts.

Initially, everyone has exactly one gift in their hand. Note that some contestants may have the same type of gifts. Specifically, the type of the gift in the $$$i$$$-th contestant's hand can be represented as a positive integer $$$g_i$$$. Two contestants $$$i$$$ and $$$j \ (1\le i,j \le m)$$$ share the same type of gifts if and only if $$$g_i=g_j$$$ holds.

There can be many rounds of gift exchanging between these $$$m$$$ contestants. In each round, two contestants may exchange their gifts with each other. Note that a pair of contestants can exchange gifts multiple times if they like. In the end, there will still be exactly one gift in each contestant's hand.

Let's denote $$$h_i$$$ as the type of gift in the $$$i$$$-th contestant's hand in the end. If $$$g_i\neq h_i$$$ holds, the $$$i$$$-th contestant will be happy, because they have a different type of gift, otherwise they will be unhappy. Your task is to write a program to help them exchange gifts such that the number of happy contestants is maximized. For example, if $$$g=[3,3,2,1,3]$$$ and $$$h=[1,2,3,3,3]$$$, there will be $$$4$$$ happy contestants.

Since $$$m$$$ can be extremely large, you will be given $$$n$$$ sequences $$$s_1,s_2,\dots,s_n$$$, and the sequence $$$g$$$ is equal to $$$s_n$$$. The $$$i$$$-th $$$(1\le i \le n)$$$ sequence will be given in one of the following two formats:

• "1 k q[1..k]" ($$$1\leq k\leq 10^6$$$, $$$1\leq q_i\leq 10^9$$$): It means $$$s_i=[q_1,q_2,\dots,q_k]$$$.
• "2 x y" ($$$1\leq x,y\leq i-1$$$): It means $$$s_i=s_x+s_y$$$. Here "$$$+$$$" denotes concatenation of sequences, for example $$$[3,3,2]+[2,2,3,3]=[3,3,2,2,2,3,3]$$$.

The input contains multiple cases. The first line of the input contains a single integer $$$T$$$ ($$$1 \leq T \leq 10\,000$$$), the number of cases.

For each case, the first line of the input contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$), denoting the number of sequences. Each of the next $$$n$$$ lines describes a sequence in one of the two formats defined in the problem statement, where the $$$i$$$-th ($$$1\le i \le n$$$) line describes the sequence $$$s_i$$$.

It is guaranteed that the sum of all $$$n$$$ over all cases does not exceed $$$10^6$$$, and the sum of $$$k$$$ over all cases does not exceed $$$10^6$$$. It is also guaranteed that no sequence has a length that exceeds $$$10^{18}$$$.

For each case, print a single line containing a single integer denoting the maximum number of happy contestants.

2
1
1 5 3 3 2 1 3
3
1 3 3 3 2
1 4 2 2 3 3
2 1 2

4
6