void rec(int mask) {
    if (sz == (1 << n) * n)
    {
        cout << sz << endl;
        for (int i = 0; i < sz; ++i) {
            if (i) cout << " ";
            cout << pos[i] + 1;
        }
        cout << endl;
        exit(0);
    }
    for (int i = 0; i < n; ++i) {
        if ((mask >> i) & 1) continue;
        int new_mask = mask ^ (1 << i);
        if (!used[new_mask][i]) {
            used[new_mask][i] = 1;
            pos[sz++] = i;
            rec(new_mask);
            used[new_mask][i] = 0;
            --sz;
        }
    }
    for (int i = 0; i < n; ++i) {
        if (!((mask >> i) & 1)) continue;
        int new_mask = mask ^ (1 << i);
        if (!used[new_mask][i]) {
            used[new_mask][i] = 1;
            pos[sz++] = i;
            rec(new_mask);
            used[new_mask][i] = 0;
            --sz;
        }
    }
}