For an operation \((x, y)\), if \(x \neq y\), the operation is invertible and the inverse is itself. Therefore, if applying invertible operations \(i_1, i_2, \ldots, i_k\) in order to string \(T\) yields string \(T'\), then applying operations \(i_k, \ldots, i_2, i_1\) in order to \(T'\) yields \(T\).

Construct the sequence of operations from both ends as follows.

• Apply operations to \(S\) to increase the number of \(1\)s as much as possible.
• For each \(i\) in \(T\), if \(T_i = 0\) and \(S_i = 1\) and operation \((i, i)\) exists, decide to apply operation \((i, i)\) last and set \(T_i = 1\).
• Apply operations to \(T\) to increase the number of \(1\)s as much as possible.

Then, if \(S = T\), the conversion has been performed correctly.

Each operation increases the number of \(1\)s in \(S\) or \(T\) by \(1\), so the number of operations is at most \(2N\).