http://poj.openjudge.cn/practice/C26D/

#include <bits/stdc++.h>
using namespace std;

static inline void appendInt(string &out, int x) {
    char buf[20];
    int len = 0;
    if (x == 0) {
        buf[len++] = '0';
    } else {
        while (x > 0) {
            buf[len++] = char('0' + x % 10);
            x /= 10;
        }
        reverse(buf, buf + len);
    }
    out.append(buf, buf + len);
}

struct Solver {
    int n, q;
    int P, R;
    bool powerOfTwo;

    vector<int> a, pos;

    // trans[0]: low -> high
    // trans[1]: high -> low
    set<int> trans[2];

    bool good(int x, int y) const {
        return (x ^ y) < n;
    }

    int type(int x) const {
        return x >= P;
    }

    bool validK(int k) const {
        return 2 <= k && k <= n - 2;
    }

    void addK(int k) {
        if (powerOfTwo || !validK(k)) return;

        int t1 = type(a[k]);
        int t2 = type(a[k + 1]);

        if (t1 != t2) {
            trans[t1].insert(k);
        }
    }

    void delK(int k) {
        if (powerOfTwo || !validK(k)) return;

        int t1 = type(a[k]);
        int t2 = type(a[k + 1]);

        if (t1 != t2) {
            trans[t1].erase(k);
        }
    }

    void init(int n_, int q_, const vector<int> &arr) {
        n = n_;
        q = q_;

        a.assign(n + 1, 0);
        pos.assign(n, 0);

        for (int i = 1; i <= n; i++) {
            a[i] = arr[i];
            pos[a[i]] = i;
        }

        powerOfTwo = (n & (n - 1)) == 0;

        trans[0].clear();
        trans[1].clear();

        if (powerOfTwo) {
            P = n;
            R = 0;
            return;
        }

        P = 1;
        while ((P << 1) < n) P <<= 1;
        R = n - P;

        for (int k = 2; k <= n - 2; k++) {
            addK(k);
        }
    }

    void doSwap(int u, int v) {
        if (u == v) return;

        vector<int> ks = {u - 1, u, v - 1, v};
        sort(ks.begin(), ks.end());
        ks.erase(unique(ks.begin(), ks.end()), ks.end());

        for (int k : ks) delK(k);

        int x = a[u];
        int y = a[v];

        swap(a[u], a[v]);
        pos[x] = v;
        pos[y] = u;

        for (int k : ks) addK(k);
    }

    void outputOne(string &out) const {
        out += "1\n\n";
    }

    void outputTwo(string &out, int k) const {
        out += "2\n";
        appendInt(out, k);
        out.push_back('\n');
    }

    void outputZero(string &out) const {
        out += "0\n";
    }

    void answer(string &out) const {
        if (powerOfTwo || good(a[1], a[n])) {
            outputOne(out);
            return;
        }

        int firstType = type(a[1]);

        // If there is an inner adjacent pair with type:
        // type(a1) -> type(an), it is a valid split.
        if (!trans[firstType].empty()) {
            outputTwo(out, *trans[firstType].begin());
            return;
        }

        // No such type transition exists.
        // Let h be the high endpoint, h = P + z.
        int highEndpoint = firstType ? a[1] : a[n];
        int z = highEndpoint - P;

        if (R >= 2) {
            // z and z^1 are two different low values compatible with highEndpoint.
            int c1 = z;
            int c2 = z ^ 1;

            int k;

            if (firstType == 1) {
                // a1 is high, an is low.
                // Interior order is low...low high...high.
                // Low positions are 2..P.
                // We need a compatible low value not at position P.
                int val = (pos[c1] != P ? c1 : c2);
                k = pos[val];
            } else {
                // a1 is low, an is high.
                // Interior order is high...high low...low.
                // Low positions start at R+1.
                // We need a compatible low value not at position R+1.
                int val = (pos[c1] != R + 1 ? c1 : c2);
                k = pos[val] - 1;
            }

            outputTwo(out, k);
            return;
        }

        // R == 1.
        // The only low value compatible with the high endpoint is 0.
        int pos0 = pos[0];

        if (firstType == 1) {
            // a1 high, an low.
            // Need 0 not to be the last low position P.
            if (pos0 == P) {
                outputZero(out);
            } else {
                outputTwo(out, pos0);
            }
        } else {
            // a1 low, an high.
            // Need 0 not to be the first low position R+1 = 2.
            if (pos0 == R + 1) {
                outputZero(out);
            } else {
                outputTwo(out, pos0 - 1);
            }
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    string out;
    out.reserve(1 << 22);

    while (T--) {
        int n, q;
        cin >> n >> q;

        vector<int> arr(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> arr[i];
        }

        Solver solver;
        solver.init(n, q, arr);

        solver.answer(out);

        for (int i = 0; i < q; i++) {
            int u, v;
            cin >> u >> v;

            solver.doSwap(u, v);
            solver.answer(out);
        }
    }

    cout << out;
    return 0;
}