I've tested all inputs from other themes, but still got wa in 3rd. Help, please!
The algorithm based on the half-invariant idea.

#include <iostream>
#include <fstream>
#include <string>
#include <math.h>
#include <sstream>
using namespace std;


int main(){
    int n, m;
    cin >> n >> m;
    bool **e = new bool*[2*n];
    for (int i=0; i<2*n; i++){
        e[i] = new bool[2*n];
        for (int j=0; j<2*n; j++){
            e[i][j] = false;
        }
    }
    int v1, v2;
    for (int i=0; i<m; i++){
        cin >> v1 >> v2;
        int tmp;
        if (v1 > v2){
            tmp = v1;
            v1 = v2;
            v2 = tmp;
        }
        e[v1-1][v2-1] = true;
        e[v2-1][v1-1] = true;
    }
    int inv=0;
    for (int i=0; i<n; i++){
        for (int j=i+1; j<n; j++){
            if (e[i][j]) inv++;
            if (e[n+i][n+j]) inv++;
        }
    }
    int *t =new int[2*n];
    for (int i=0; i<2*n; i++){
        t[i] = i;
    }
    while (inv > 0){
        int s = 0;
        for (int i=0; i<n; i++){
            int i_out = 0;
            int i_in = 0;
            for (int k=0; k<n; k++){
                if (e[t[i]][t[k]] || e[t[k]][t[i]]){
                    i_in++;
                }
                if (e[t[i]][t[k+n]] || e[t[k+n]][t[i]]){
                    i_out++;
                }
            }
            for (int j=n; j<2*n; j++){
                int j_out = 0;
                int j_in = 0;
                for (int k=0; k<n; k++){
                    if (e[t[k+n]][t[j]] || e[t[j]][t[k+n]]){
                        j_in++;
                    }
                    if (e[t[k]][t[j]] || e[t[j]][t[k]]){
                        j_out++;
                    }
                }
                if (e[t[i]][t[j]] || e[t[j]][t[i]]){
                    j_out--;
                    j_out--;
                }
                if (i_in + j_in > i_out + j_out){
                    s++;
                    inv -= (i_in + j_in - i_out - j_out);
                    int tmp = t[i];
                    t[i] = t[j];
                    t[j] = tmp;
                }
                if (s == 1) break;
            }
            if (s == 1) break;
        }
        if (s == 0){
            cout << "IMPOSSIBLE\n";
            return 0;
        }
    }
    string tour1, tour2;
    tour1 = "";
    tour2 = "";
    for (int i=0; i<n; i++){
        for (int j=i+1; j<n; j++){
            if (t[i]>t[j]){
                int tmp = t[i];
                t[i] = t[j];
                t[j] = tmp;
            }
            if (t[i+n]>t[j+n]){
                int tmp = t[i+n];
                t[i+n] = t[j+n];
                t[j+n] = tmp;
            }
        }
    }
    for (int i=0; i<n; i++){
        std::ostringstream ostr;
        ostr << (t[i]+1);
        std::string theNumberString = ostr.str();
        tour1 = tour1 + theNumberString + " ";
    }
    for (int i=0; i<n; i++){
        std::ostringstream ostr;
        ostr << (t[n+i]+1);
        std::string theNumberString = ostr.str();
        tour2 = tour2 + theNumberString + " ";
    }
    cout << tour1 << endl << tour2 << endl;
    return 0;
}