Longest Standby

In the programming language Sleep++ the program consists of (n) functions. For each function (i) ((1 \le i \le n)), we are given an integer (e_i) (either 0 or 1) and a sequence (Q_i = (Q_{i,1}, Q_{i,2}, \dots, Q_{i,l_i})) of subfunction indices. These sequences satisfy the following conditions:

1. (n \ge 1).
2. For every (i), (e_i \in {0,1}).
3. For every (i), the elements in (Q_i) are distinct and each is an integer in the range ([i+1, n]).
4. For every (j) with (2 \le j \le n), there is exactly one (i) ((1 \le i \le n)) for which (j) appears in (Q_i).

The execution (or call) of a function (i) is defined as follows:

• When function (i) is called, if (e_i = 0) then the value (r_i) is set to (1). Otherwise (if (e_i=1)) the program requires an input: a positive integer (r_i).

• If (Q_i) is empty, the program waits for (r_i) seconds. Otherwise, it repeats the following process exactly (r_i) times: call each function whose index appears in (Q_i) in order.

(NOTE: Apart from the waiting period, all operations including function calls and inputs are instantaneous.)

Two players, (\omega) and (\aleph), choose one function from their respective Sleep++ programs and then call it simultaneously at time 0. During execution, at each time (t \ge 0) each player sees all the numbers that the opponent input at times ([0,t-1]) and may adjust their own inputs at time (t). However, inputs at the same time are not known to the opponent. The player whose function call finishes earlier loses; if they finish simultaneously the outcome is a draw.

Being perfect logicians, both players consider the game fair only if neither has a winning strategy. In particular, if one player’s function call allows a forced win, the game is not fair.

In a game round the following happens on (\omega)’s side: (\omega) has written a Sleep++ program with (n) functions and performs (m) operations. There are two types of operations:

1. Operation 1: Given an integer (k), change (e_k) to (1 - e_k).
2. Operation 2: Given an integer (k), play one round of "Longest Standby" in which (\omega) calls function (k) at time 0.

(\aleph), a minimalist, intends to design a Sleep++ program with as few functions as possible so that she can choose one function which makes the game fair. It can be shown that for every game round such a program always exists. Your task is to help (\aleph) determine the minimum number of functions her program must have for the game to be fair.

A key observation is that the waiting time of a function call can be expressed in a linear form. For any function (i), define its structural value (F(i)) recursively as follows:

• If (Q_i) is empty then (F(i)=1).
• Otherwise, (F(i)= \sum_{j \in Q_i} F(j)).

Notice that (F(i)) equals the number of leaf functions in the subtree (defined by the call relation) of function (i).

For the game to be fair, both players must have the same degree of control over their waiting times. In particular, if (\omega)'s chosen function (k) is of type 1 (i.e. (e_k=1)), then (\aleph) must choose a function that also is type 1, and vice versa. Moreover, if (\omega)'s function has a structural value of (v = F(k)), then a fair game is achieved when both players’ waiting time expressions share the same structural multiplier. (\aleph) may design her program arbitrarily (while satisfying the Sleep++ rules) and choose any one of its functions. It turns out that the minimum number of functions needed is given by:

[ \text{ans} = \begin{cases} 1 & \text{if } v=1,\ v+1 & \text{if } v>1. \end{cases} ]

Note that the operations only modify (e_i) values while the (Q_i) structure remains fixed. You are to process (m) operations. For each operation of type 2, output the minimum number required for (\aleph)'s program based solely on the structural value of the chosen function (k) (which is the number of leaves in its subtree).

\textbf{Input / Output Details:}

The input begins with two integers (n) and (m). Then follow (n) integers representing (e_1, e_2, \dots, e_n). After that, for each (i) from 1 to (n), there is a line describing function (i): the first integer is (l_i) (the number of subfunctions), followed by (l_i) integers denoting the elements of (Q_i). Finally, there are (m) lines each describing an operation. Each operation is given as two integers: the first is the operation type (1 or 2), and the second is (k).

For each operation of type 2, output a single line containing the minimum number of functions required for (\aleph)'s program.

\textbf{Example:}

Consider the following input:

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

Here, (n=5) and (m=5). The structure is as follows:

• Function 1 calls functions 2 and 3;
• Function 2 calls function 4;
• Function 3 is a leaf;
• Function 4 calls function 5;
• Function 5 is a leaf.

The structural values are:

(F(5)=1,\quad F(4)=1,\quad F(2)=1,\quad F(3)=1,\quad F(1)= F(2)+F(3)=2.)

The operations are:

1. Query on function 1: Since (F(1)=2>1), answer = (2+1=3).
2. Flip (e_3) (no effect on structure).
3. Query on function 3: (F(3)=1), answer = 1.
4. Query on function 4: (F(4)=1), answer = 1.
5. Flip (e_1).

Thus, the outputs for the queries are:

3
1
1

Your task is to implement a program that processes the operations and outputs the answer for every type 2 query.

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of functions and the number of operations).

The second line contains \(n\) integers: \(e_1,e_2,\dots,e_n\), where each \(e_i\) is either 0 or 1.

Then \(n\) lines follow. The \(i\)-th of these lines describes the \(i\)-th function. It begins with an integer \(l_i\) (the number of subfunctions), followed by \(l_i\) distinct integers \(Q_{i,1},Q_{i,2},\dots,Q_{i,l_i}\) (each between \(i+1\) and \(n\)).

Finally, there are \(m\) lines, each describing an operation. Each operation is described by two integers: the first is the operation type (either 1 or 2), and the second is an integer \(k\) (\(1 \le k \le n\)).

outputFormat

For each operation of type 2, output a single integer on a separate line representing the minimum number of functions required for \(\aleph\)'s program.

sample

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

3
1
1

</p>