Problem Description

Elf programmers $\omega$ and $\aleph$ have infinite lifespans, so besides writing code, they often play some competitive games to kill time. Even so, they still have too much time, so they invented a game specifically for killing time: Longest Standby.

To understand the rules of Longest Standby, you first need to know the rules of the programming language Sleep++ used by the elves:

• A program consists of $n$ functions. The $i$-th function $(1 \le i\le n)$ has a type $e_i$ and a subfunction index sequence $Q_i = (Q_{i,1},Q_{i,2},\cdots,Q_{i,l_i})$. $Q_i$ can be empty, in which case $l_i$ is $0$.

• $n$ and all $e_i$ and $Q_i$ can be chosen arbitrarily by the programmer, but they must satisfy all of the following conditions:

  • $n\ge 1$;
  • $\forall 1 \le i \le n$, $e_i \in \{0, 1\}$;
  • $\forall 1 \le i \le n$, the elements in $Q_i$ are pairwise distinct and are all integers in $[i + 1, n]$;
  • $\forall 2 \le j \le n$, exactly one $Q_i(1 \le i \le n)$ contains $j$.

• When calling function $i(1 \le i \le n)$, the following operations are executed in order:

  • If $e_i = 0$, set variable $r_i$ to $1$; otherwise, the programmer must immediately input a positive integer value for $r_i$.
  • If $Q_i$ is empty, the program waits for $r_i$ seconds; otherwise, repeat the following operations $r_i$ times:
    • Call the functions numbered $Q_{i,1},Q_{i,2},\cdots,Q_{i,l_i}$ in order.

• If a type $1$ function $j$ is called multiple times, then each call requires inputting $r_j$.

• We consider that in a function call, all operations other than “wait for $r$ seconds” take no time, i.e. function calls, execution, and input are completed instantly. Therefore, within a single moment, a programmer may input multiple numbers.

It can be proven that calling any function of any Sleep++ program, no matter how the inputs are set, always takes a finite amount of time.

The rules of the game “Longest Standby” are as follows:

• $\omega$ and $\aleph$ each prepare their own Sleep++ program and choose one function from their own program. They both know the structure of the other’s program and the chosen function.

• At time $0$, $\omega$ and $\aleph$ simultaneously call their chosen functions, and the game begins.

• At time $t$ ($t \ge 0$), both sides can see all numbers the other side input at times $0$ to $(t - 1)$, and adjust the numbers they input at time $t$ accordingly, but neither side can know the number the other side inputs at time $t$.

• The side whose function call ends first loses the game, and the other side wins. If both calls end at the same time, it is a draw.

Both $\omega$ and $\aleph$ are extremely smart. In their view, if either side has a sure-win strategy, then the game is unfair. In other words, a game is fair if neither side has a sure-win strategy.

$\omega$ wrote a Sleep++ program with $n$ functions and performed $m$ operations. There are two kinds of operations:

• Operation 1: given $k$, change $e_k$ to $(1 - e_k)$;
• Operation 2: given $k$, play one round of “Longest Standby” with $\aleph$. At the start, $\omega$ will call their own function $k$.

$\aleph$ believes in minimalism. For each game, it wants to design a program with as few functions as possible, such that choosing some function in it makes the game fair. Can you help it find the minimum number of functions required?

It can be proven that $\aleph$ can always design a program and choose one function in it such that the game is fair.

Input Format

The first line contains two positive integers $n,m$, representing the number of functions in $\omega$’s program and the number of operations.

The next $n$ lines describe function $i$ in $\omega$’s program. Line $i$ contains several integers:

• The first two integers $e_i, l_i$ denote the function type and the length of the subfunction index sequence;
• The next $l_i$ integers $Q_{i,1},Q_{i,2},\cdots,Q_{i,l_i}$ describe the subfunction index sequence.

The next $m$ lines each contain two integers $o_j, k_j$, describing one operation, where $o_j = 1$ denotes operation 1 and $o_j = 2$ denotes operation 2.

Output Format

For each operation 2, output one line with one integer, representing the minimum number of functions required in $\aleph$’s program.

3 6
0 2 2 3
0 0
0 0
2 1
1 3
2 1
1 3
1 2
2 1

3
3
1

Hint

[Sample 1 Explanation]

• For the first two games, $\aleph$ can provide a program that is exactly the same as $\omega$’s and call function $1$ when the game starts. It can be proven that there is no solution with fewer functions.

• For the third game, $\aleph$ can provide a program that contains only one type $1$ function, and call function $1$ when the game starts.

  • At time $0$, $\omega$ inputs $r_2$ in their program, and $\aleph$ inputs $r_1$ in their program.
    • Note: the $r$ variables are independent between $\omega$’s and $\aleph$’s programs, and do not affect each other.
  • After the input is completed, $\omega$’s program ends at time $(r_2 +1)$, and $\aleph$’s program ends at time $r_1$.
  • Since at time $0$ neither side knows the other’s decision, they cannot guarantee the relationship between $(r_2 + 1)$ and $r_1$, so neither side has a sure-win strategy, and the game is fair.

[Sample 2]

See sleep2.in/ans in the attachment.

This testdata satisfies special property AD.

[Sample 3]

See sleep3.in/ans in the attachment.

This testdata satisfies special property BD.

[Sample 4]

See sleep4.in/ans in the attachment.

This testdata satisfies special property D.

[Sample 5]

See sleep5.in/ans in the attachment.

This testdata satisfies special property C.

[Subtasks]

For all testdata,

• $1 \le n \le 5\times 10^5$, $1 \le m \le 2\times 10^5$;
• $\forall 1 \le i \le n$, $e_i\in \{0, 1\}$, $0 \le l_i <n$;
• $\forall 1 \le i \le n,1 \le j \le l_i$, $i < Q_{i,j} \le n$;
• $\forall 1 \le i \le n, 1 \le p < q \le l_i$, $Q_{i,p}\neq Q_{i,q}$;
• $\forall 2 \le j \le n$, exactly one $Q_i(1 \le i \le n)$ contains $j$;
• $\forall 1 \le j \le m$, $1 \le o_j \le 2$, $1 \le k_j \le n$.

Special property A: guaranteed that

• At any time, $e_1$ is always $0$;
• $\forall 2\le i \le n$, $l_i \le 1$;
• In operation 2, $k$ is always $1$.

Special property B: guaranteed that

• In operation 2, $k$ satisfies that at that time $e_k$ is $1$.

Special property C: guaranteed that

• $\forall 2\le i \le n$, $i \in Q_{\lfloor \frac{i}{2}\rfloor}$;
• $\forall 1 \le i \le n$, the sequence $Q_i$ is strictly increasing.

Special property D: guaranteed that

• There are at most $10$ operation 2 queries;
• In operation 2, $k$ is always $1$.

Translated by ChatGPT 5