Greedy solution. Continue constructing $$$b$$$ as small as possible.

If $$$a_{1} = 1$$$, $$$b_{1} = 2$$$. Else, $$$b_{1} = 1$$$.

For $$$i \ge 2$$$, if $$$a_{i} = b_{i-1} + 1$$$, $$$b_{i} = b_{i-1} + 2$$$. Else, $$$b_{i} = b_{i-1} + 1$$$.

$$$b_{n}$$$ calculated by this process is the answer.

Time complexity is $$$\mathcal{O}(n)$$$ per test case.

Sorry for everyone who got FSTs :( We tried our best to make pretest strong especially for this problem, but it wasn't enough.

Denote $$$T = S_{1} \cup S_{2} \cup \cdots \cup S_{n}$$$, then $$$S \subset T$$$. Since $$$S \neq T$$$, $$$i \in T$$$ and $$$i \notin S$$$ for some $$$i$$$.

Given an integer $$$i$$$, can you calculate the maximum size of $$$S$$$, such that $$$i \notin S$$$?

$$$i \in T$$$ and $$$i \notin S$$$ for some $$$i$$$. Here $$$1 \le i \le 50$$$.

For fixed $$$i$$$, select of all the sets among $$$S_{1}, S_{2}, \cdots, S_{n}$$$ which don't contain $$$i$$$. Size of their union will be the maximum size of $$$S$$$ such that $$$i \notin S$$$.

If we do this for all $$$i$$$ in $$$T$$$, maximum of them is the answer.

Time complexity is $$$\mathcal{O} \left( N \cdot \max \left( s_{i, j} \right) ^{2}\right)$$$.

Fix the topmost card you'll pick in the initial deck.

Let's denote $$$i$$$-th card in the initial deck as card $$$i$$$.

Let the topmost card you'll pick in the initial deck as card $$$i$$$.

For all cards under card $$$i$$$ in initial deck, you can choose all and only cards with the positive value at odd index.

Proof: Here is the strategy. Before you pick card $$$i$$$, if positive card(under card $$$i$$$ in initial deck) in odd index exists, choose it. Repeat this until all positive cards(under card $$$i$$$ in initial deck) are in even index. Then if you choose card $$$i$$$, all index of positive cards(under card $$$i$$$ in initial deck) will be decreased by $$$1$$$, and will become odd. Now, choose them from the bottom to top, so that the choosing won't change the other positive cards' index.

Denote $$$prf_{j}$$$ as the sum of positive numbers among $$$a_{j}, a_{j+1}, \cdots, a_{n}$$$, and $$$prf_{n+1} = 0$$$. Since $$$prf_{j} = prf_{j+1} + \max \left( 0, a_{j}\right)$$$, $$$prf$$$ can be calculated in $$$\mathcal{O}(n)$$$.

You should necessarily pick card $$$i$$$ in index of $$$i$$$, and can pick all positive cards under card $$$i$$$ in initial deck, so your maximum final score will be $$$(i \% 2 == 1 ? a_{i} : 0) + prf_{i+1}$$$.

The answer is $$$\max \left( (i \% 2 == 1 ? a_{i} : 0) + prf_{i+1} \, | \, 1 \le i \le n \right)$$$.

There are lots of other solutions too.

Try to solve the problem for single root.

For any vertex $$$v$$$ which isn't the root, denote $$$par_{v}$$$ as the parent of $$$v$$$. Then value of $$$a_{v} \oplus a_{par_{v}}$$$ only changes if we perform the operation on $$$v$$$.

Since $$$x_{1} \oplus x_{2} \oplus \cdots \oplus x_{m} \le x_{1} + x_{2} + \cdots + x_{m}$$$ for any numbers $$$x_{1}, x_{2}, \cdots, x_{m}$$$, we can assume that there is at most operation performed in same vertex.

Let's solve the problem for single root first.

Denote the operation in the statement as $$$op(v, c)$$$, and size of $$$v$$$'s subtree as $$$s_{v}$$$.

The goal is to make $$$a_{v} \oplus a_{par_{v}} = 0$$$ for every non-root vertex $$$v$$$. This value is changed only when we select $$$v$$$. To make $$$a_{v} \oplus a_{par_{v}}$$$ to $$$0$$$, we should perform $$$op \left( v, a_{v} \oplus a_{par_{v}} \right)$$$ (Look Hint 3).

Therefore, the answer sill be $$$\sum_{i != root} s_{i} \times (a_{i} \oplus a_{par_{i}})$$$. Now our task is to calculate this for all roots. This can be done by lots of ways, and the following algorithm is one way.

Calculate the answer for $$$1$$$ as root first in $$$\mathcal{O}(n)$$$. Now, we will traverse the tree starting at vertex $$$1$$$ and keep updating the answer. If root changes from $$$q$$$ to $$$r$$$ ($$$q$$$ and $$$r$$$ are adjacent), every vertex except $$$q$$$ and $$$r$$$ will have same parents and subtree size, so will contribute same to the answer, so we only need to consider $$$q$$$ and $$$r$$$ to calculate the change. Edge connecting $$$q$$$ and $$$r$$$ will divide the tree into parts: each of size $$$X$$$ and $$$Y$$$. If root changes $$$q$$$ to $$$r$$$, $$$Y \times (a_{q} \oplus a_{r})$$$ will be subtracted, and $$$X \times (a_{q} \oplus a_{r})$$$ will be added to the answer. $$$X$$$ and $$$Y$$$ can be pre-calculated in $$$\mathcal{O}(n)$$$, so this update costs $$$\mathcal{O}(1)$$$.

Since changing root into the adjacent vertex costs $$$\mathcal{O}(1)$$$, answer for all roots can be calculated in $$$\mathcal{O}(n)$$$.

Let's think two permutations independently. The goal is to make sequence of operations for each permutation which have same parity of number of operations.

Try to sort single permutation of length $$$N$$$, using at most $$$3N$$$ operations. It is always possible.

If the permutation's length is odd, you can perform operation at index $$$1$$$ for $$$N$$$ times and return to the same permutation.

If the permutation's length is even, the parity of inversion number changes in each operations.

Hints above were the summary of the tutorial. Please check them.

First, let's do Hint 2. There are lots of ways to do this, and I'd like to introduce one which I thought first. It is possible to swap two elements using $$$3$$$ operations. Let's denote the two elements as $$$x$$$ and $$$y$$$, and permutation as $$$[[ A ] x [ B ] y [ C ]]$$$ ($$$[ A ], [ B ], [ C ]$$$ are subarrays). Then:

1. Perform the operation at $$$x$$$. Permutation becomes $$$[[ B ] y [ C ] x [ A ]]$$$.
2. Perform the operation at $$$y$$$. Permutation becomes $$$[[ C ] x [ A ] y [ B ]]$$$.
3. Perform the operation at $$$x$$$. Permutation becomes $$$[[ A ] y [ B ] x [ C ]]$$$.

Using this, we can sort the single permutation of length $$$N$$$ using at most $$$3N$$$ operations, since we can sort the permutation by $$$N$$$ swaps.

If this requires same parity of number of operations for $$$p$$$ and $$$q$$$, the problem is solved. At most $$$3 \max(m, n)$$$ operations are used.

Else, if $$$n$$$ or $$$m$$$ is odd, we can make the parity equal by method provided in Hint 3. At most $$$4 \max(m, n)$$$ operations are used.

Else, then $$$n$$$ and $$$m$$$ is both even. In this case, it's impossible because of Hint 4.

The overall time complexity is $$$\mathcal{O}(n + m)$$$ in this solution.

Lastly, here is the proof of Hint 4.

Proof: Let's consider the permutation of length $$$N$$$($$$N$$$ is even). Denote the permutation as $$$[[ A ] x [ B ]]$$$, and the length of $$$[ A ]$$$ and $$$[ B ]$$$ as $$$n_{A}$$$ and $$$n_{B}$$$. Here $$$n_{A} + n_{B} = N-1$$$ so one of $$$n_{A}$$$ and $$$n_{B}$$$ is even and one of them is odd. Permutation becomes $$$[[ B ] x [ A ]]$$$ after the operation.

First, the parity of inversion number from two elements of $$$[ A ]$$$ or two elements of $$$[ B ]$$$ doesn't change, because their order inside doesn't change.

Second, the parity of inversion number from one element of $$$[ A ]$$$ and one element of $$$[ B ]$$$ doesn't change, because sum of them are $$$n_{A} \times n_{B}$$$, which is even.

Third, the parity of inversion number from $$$x$$$ and one element of $$$[ A ]$$$ or $$$[ B ]$$$ changes, because sum of them are $$$n_{A} + n_{B}$$$, which is odd.

If we add these three, we can lead to the conclusion that the parity of inversion number must change. The text may look a bit complicated, but it will not be that hard if you write them in your own :)

The solution is completely different from E1. A brilliant idea is required. Maybe the fact that checker is implemented in linear time might be the hint.

Find a way changing the operation to 'swap'.

Add an extra character.

Add an extra character '$$$X$$$' in front of the permutation. Here position of $$$X$$$ won't be changed by the operation, and will always locate at left of $$$p_{1}$$$. Then in each operation, the permutation will change as: $$$[X [ A ] c [ B ]] \rightarrow [X [ B ] c [ A ]]$$$.

Now, let's consider the array made by $$$X$$$ and permutation as circular. This is possible because $$$X$$$ is always in left of $$$1$$$st element, so it marks the start of the permutation. Then $$$[X [ B ] c [ A ]]$$$ is equivalent with $$$[c [ A ] X [ B ]]$$$.

Then the operation is: $$$[X [ A ] c [ B ]] \rightarrow [c [ A ] X [ B ]]$$$, which is same with swapping $$$X$$$ and $$$c$$$.

Now we need to calculate the minimum odd number of swaps and even number of swaps(of $$$X$$$ and any element) each, turning $$$[X\,p_{1}\,p_{2}\,\cdots\,p_{n}]$$$ to one of $$$[X\,1\,2\,\cdots\,n]$$$, $$$[n\,X\,1\,2\,\cdots\,(n-1)]$$$, $$$[(n-1)\,n\,X\,1\,\cdots\,(n-2)]$$$, $$$\cdots$$$, $$$[1\,2\,\cdots\,n\,X]$$$.

To calculate the minimum number of swaps required to turn $$$[X\,p_{1}\,p_{2}\,\cdots\,p_{n}]$$$ to the given array, first renumber the initial array to $$$[X\,1\,2\,\cdots\,n]$$$, then change the given array in the same correspondence. Do permutation cycle decomposition. Then the answer is (sum of (size + 1) for cycles which have size $$$\ge$$$ 2 and don't contain $$$X$$$) + ($$$X$$$'s cycle size $$$-$$$ 1). This can be proven easily by counting the number of elements which go into the proper place in each operations.

Calculate this for all $$$[X\,1\,2\,\cdots\,n]$$$, $$$[n\,X\,1\,2\,\cdots\,(n-1)]$$$, $$$[(n-1)\,n\,X\,1\,\cdots\,(n-2)]$$$, $$$\cdots$$$, $$$[1\,2\,\cdots\,n\,X]$$$. Since we can't make the same array using different parity of number of swaps, we can achieve the goal by calculating the minimum odd number and minimum even number each.

The overall time complexity is $$$O(n^{2}+m^{2})$$$.

Try solving E1 in $$$n,\,m \le 10^{5}$$$, using at most $$$1.5 \times 10^{5}$$$ operations. It is solvable :)