P5166 xtq's Password

In third grade, xtq already showed excellent physical fitness, so the PE teacher allowed him to skip the class exercises and move freely. xtq is now observing his classmates running.

There are $n$ students lined up for running. The PE teacher gave an order, asking these $n$ students to speed up. However, because the wind was too strong, only some students heard and carried out the order. At the same time, if a student who did not hear the order observes other students carrying out the order, he will also carry out the order. Now we generalize this situation. We number the student at the front of the line as $1$, the next as $2$, and so on, with the student at the end numbered $n$. After observation, xtq provides for each student several observed targets. This means that when this student sees any one of his observed targets speed up (carry out the order), he will also speed up (carry out the order). It is guaranteed that for any student, all of his observed targets have indices smaller than his own (a student only observes some of the students in front of him). Now there are $q$ queries or modifications: Query: in the form of ```1 L R```. Answer: if the students with indices in $\left[L,R \right]$ have heard the order, at least how many more students need to hear the order to make everyone carry out the order. Modification: in the form of ```2 L R x```. For each student in $\left[L,R \right]$, add student $x$ as one of his observed targets. It is guaranteed that $x < L$. If someone in the interval already has student $x$ as an observed target, ignore it.

The first line contains two integers $n,q$. In the next $n$ lines, the first integer of each line is $a_i$, meaning student $i$ is observed by a total of $a_i$ students. Then follow $a_i$ integers, which are the indices of the students who observe student $i$. If $a_i=0$, it means no one observes this student. Since a student can only be observed by students behind him, the input indices are guaranteed to be greater than this student's own index. #### Note that the input indices are the indices of students who observe student $i$, not the indices of students observed by student $i$. Then follow $q$ lines, each being a query or a modification, in the formats described above.

For each query operation, output the minimum number of additional students who need to know the order so that eventually every student carries out the teacher's order.

【Sample Explanation】 In the sample, student $1$ is observed by student $3$, student $2$ is observed by student $3$, and student $3$ is observed by student $4$. For the first query ```1 2 3```: this means students $2$ and $3$ heard the teacher's order. Since student $3$ is observed by student $4$, after student $3$ speeds up, student $4$ will also speed up. Therefore, we need to tell student $1$ what the order is, so that all students receive the order. 【Constraints】 |ID|n|Special Property| | ------ | ------ | ------ | |1|$10$|Yes| |2|$10$|No| |3|$500$|Yes| |4|$5000$|No| |5|$5000$|No| |6|$50000$|Yes| |7|$50000$|No| |8|$3 \times 10^5$|Yes| |9|$3 \times 10^5$|No| |10|$3 \times 10^5$|No| Special Property: the number of modification operations does not exceed $100$. For $100\%$ of the testdata, $n,q\le 3 \times 10^5$, $\sum a_i\le 10^7$. Because the input and output size of this problem is large, please do not use cin/cout. Translated by ChatGPT 5