Problem: A programming coach has n students to teach. We know that n is divisible by 3. Let's assume that all students are numbered from 1 to n, inclusive.

Before the university programming championship the coach wants to split all students into groups of three. For some pairs of students we know that they want to be on the same team. Besides, if the i-th student wants to be on the same team with the j-th one, then the j-th student wants to be on the same team with the i-th one. The coach wants the teams to show good results, so he wants the following condition to hold: if the i-th student wants to be on the same team with the j-th, then the i-th and the j-th students must be on the same team. Also, it is obvious that each student must be on exactly one team.

Help the coach and divide the teams the way he wants.

Input

The first line of the input contains integers n and m (3 ≤ n ≤ 48, <image>. Then follow m lines, each contains a pair of integers ai, bi (1 ≤ ai < bi ≤ n) — the pair ai, bi means that students with numbers ai and bi want to be on the same team.

It is guaranteed that n is divisible by 3. It is guaranteed that each pair ai, bi occurs in the input at most once.

Output

If the required division into teams doesn't exist, print number -1. Otherwise, print <image> lines. In each line print three integers xi, yi, zi (1 ≤ xi, yi, zi ≤ n) — the i-th team. 

If there are multiple answers, you are allowed to print any of them.

Examples

Input

3 0


Output

3 2 1 


Input

6 4
1 2
2 3
3 4
5 6


Output

-1


Input

3 3
1 2
2 3
1 3


Output

3 2 1 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
/*
#include<boost/multiprecision/cpp_int.hpp>
namespace mp=boost::multiprecision;
*/
using namespace std;
#define ll int
#define lo mp::cpp_int
#define pb push_back
#define pob pop_back
#define mk make_pair
#define endl "\n"
#define ce(x) cout << x <<"\n"
#define fill(s,v) memset(s,v,sizeof(s))
#define speed  { ios_base::sync_with_stdio(false); cin.tie(0); }
#define deb(x) cout<<#x<<" "<<x<<endl; 
#define INFINITE 1000000009
#define ull unsigned long long int
#define take(a,n) for(ll pp=0;pp<n;pp++) { cin>>a[pp]; }
#define take2(a,n) for(ll p=0;p<n;p++) { ll temp;cin>>temp;a.pb(temp); }
#define f(i,n) for(ll i=0;i<n;i++)
#define f1(i,a,n) for(ll i=a;i<n;i++)
#define show(a,n) for(ll p=0;p<n;p++) cout<<a[p]<<" ";
#define _ <<" "<<
#define nl cout<<endl;
#define sq(x) ((x)*(x))
#define call(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define ff first
#define ss second
#define lld long double
#define sc(n) scanf("%lld",&n);
#define de2(x,y) cout<<#x<<" = "<<(x) <<' '<< #y<<" = "<<y<<endl;typedef pair<int, int> pii;
#define copy(b,a,n) for(ll i=0;i<n;i++) b[i]=a[i];
#define clock() clock_out()
#define tc(tt) \
    ll tt;    \
    cin >> tt; \
    for (int _tt = 0; _tt < tt; _tt++) 
typedef vector<vector<ll>> matrix ;  
typedef pair<ll,ll> pii;
typedef vector<pii> vii;
typedef vector<ll> vi;   
const ll dx[4] = {-1, 0, 1, 0};
const ll dy[4] = {0, -1, 0, 1};
const ll mod = 1000000007;
ll gcd(ll a,ll b){if(!b)return a;return gcd(b,a%b);} 
ll power_mod(ll x,ll y,ll p){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;} 
ll modexpo(ll x,ll n,ll M){if(n==0)return 1;else if(n%2 == 0)return modexpo((x*x)%M,n/2,M);else return(x*modexpo((x*x)%M,(n-1)/2,M))%M;}
ll lcm(ll a, ll b){return (a*b)/gcd(a, b);}
ll sumofdigits(ll n){ll out=0;while(n){out+=(n%10);n/=10;}return out;}
bool isPrime(ll n){if (n <= 1)  
    return false; if (n <= 3)  return true; if (n%2 == 0 || n%3 == 0) return false; 
    for (ll i=5; i*i<=n; i=i+6) if (n%i == 0 || n%(i+2) == 0) return false;return true;} 
// ll power(ll a,ll b){if(b==0)return 1;if(b&1)return a*power(a,b-1);ll res=power(a,b/2);return res*res;}
ll bexpo(ll x,ll n){if(n==0)return 1;else if(n%2==0)return bexpo(x*x,n/2);else return x*bexpo(x*x,(n-1)/2);}
ll log(ll d){return log2(d);}
bool isPower(ll x, ll y){if(x==1) return (y==1); ll pow=1; while(pow<y) pow*=x; return(pow == y);}  
bool isPerfectSquare(long double x){long double sr = sqrt(x);return ((sr - floor(sr)) == 0);}   
bool compare(const pair<ll,ll> &a, const pair<ll,ll> &b) { return (a.second < b.second);} 
ll isPalindrome(string s){ll l=0;ll h=s.size()-1;while(h>l){if(s[l++]!=s[h--])return 0;}return 1;} 
ll setbits(ll n) { if(n==0)return 0; else return 1+setbits(n&(n-1)); } 
ll modInverse(ll A,ll M){return modexpo(A,M-2,M);}
ll suma(ll *a,ll n){ll sum=0;for(ll i=0;i<n;i++)sum+=a[i];return sum;}
// void clock_out(){
//   cerr<<"\nTime Elapsed : " << 1.0*clock() / CLOCKS_PER_SEC << " s\n";
// }
//------modular inverse by extended euclid-------//

// ll d, x, y;
// void extendedEuclid(ll A, ll B) {
//  if(B == 0) {
//  d = A;
//  x = 1;
//  y = 0;
//  }
//  else {
//  extendedEuclid(B, A%B);
//  ll temp = x;
//  x = y;
//  y = temp - (A/B)*y;
//  }
// }

// ll modInverse2(ll A, ll M){
// extendedEuclid(A,M);
// return (x%M+M)%M;
// }

//---------------------------------//

//---------------matrix exponentiation-------------------//

// matrix mul(matrix a,matrix b){
//   matrix res(n+1,vector<ll>(n+1));
//   f(i,n)f(j,n)f(k,n)res[i][j]=(res[i][j]%mod+((a[i][k]%mod)*(b[k][j]%mod))%mod)%mod;
//    return res;
// }
// matrix pow(matrix A,ll p) {
//     if(p==1) return A;
//     matrix res=pow(A,p/2) ;
//     res=mul(res,res);
//     if(p&1) res=mul(res,A) ;
//     return res;
// }

//-------------------------------------------------//

vector<ll> factorize(ll n) {
    vector<ll> res;
    for (ll i = 2; i * i <= n; ++i) {
        while (n % i == 0) {
            res.push_back(i);
            n /= i;
        }
    }
    if (n != 1) {
        res.push_back(n);
    }
    return res;
}

vector<ll> divisors(ll n){ 
    vector<ll> res;
    for (ll i=1; i<=sqrt(n); i++){ 
        if (n%i == 0){ if (n/i == i){ res.pb(i); } else{ res.pb(n/i); res.pb(i); } } 
    } 
    return res;
}   
vector<ll> primeFactors(ll n){  
    if(n==1) return vector<ll>(1,1);
    bool idx[1]={false};
    vector<ll> res;
    while (n%2 == 0){  
        if(!idx[1]){idx[1]=true;res.pb(2);}
        n = n/2;  
    }  
    for (ll i=3;i*i<=n; i+=2){
        bool once=false;
        while (n%i==0){ if(!once){res.pb(i);once=true;} n=n/i; }  
    }  
    if (n > 2)res.pb(n);
    return res;
}

//--------------------------------------------//

ll dxx[] = {1, 1, 0, -1, -1, -1, 0, 1};
ll dyy[] = {0, 1, 1, 1, 0, -1, -1, -1};

//----check if a point is in range-----///
///__builtin_ctz(x) --> get power of 2 dude !!!! 

bool check(ll x,ll y,ll n,ll m){return(x>=0&&x<n&&y>=0&&y<m);}

const int FULL_MASK = (1 << 10) - 1;
#define pi 3.1415926535897932

vector<vector<ll>> ed;

void bfs(ll s, vector<ll> &d) {
    d[s] = 0;
    queue<ll> q;
    q.push(s);
    while (!q.empty()) {
        ll v = q.front();
        q.pop();
        for (auto to : ed[v]) {
            if (d[to] == 1e9) {
                d[to] = d[v] + 1;
                q.push(to);
            }
        }
    }
} 
ll maxSubArraySum(ll a[],ll size) 
{ 
    ll max_so_far = a[0]; 
    ll curr_max = a[0]; 
  
   for (ll i = 1; i < size; i++) 
   { 
        curr_max = max(a[i], curr_max+a[i]); 
        max_so_far = max(max_so_far, curr_max); 
   } 
   return max_so_far; 
} 

struct node{
    ll a,b,c,d;
};

void solve(){
    ll n,m; cin>>n>>m;
    if(n==1 || m==1){
        ce("YES"); return;
    }
    if(n==2 && m==2){
        ce("YES"); return;
    }
    ce("NO");
}

   const int MAX=48;
vector<int> adj[MAX+5],temp,ones;
int n,m,a,b,cnt,cntr,vis[MAX+5],sz[MAX+5];
vector<vector<int> >v,twos;
 
void dfs(int u){
vis[u]=1;
temp.push_back(u);
for(int i=0;i<adj[u].size();i++){
    if(!vis[adj[u][i]])
        dfs(adj[u][i]);
}
}
 
int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    a=b=0;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
        dfs(i);
        if(temp.size()>3) return cout<<"-1",0;
        if(temp.size()==1){
            a++;
            ones.push_back(temp[0]);
        }
        else if(temp.size()==2){
            b++;
            twos.push_back(temp);
        }
        else {
            v.push_back(temp);
        }
        temp.clear();
        }
    }
    if((a<b)||(a-b)%3) return cout<<"-1",0;
    for(int i=0;i<twos.size();i++){
        for(int j=0;j<twos[i].size();j++){
            cout<<twos[i][j]<<" ";
        }
        cout<<ones[cntr++]<<endl;
    }
    a=0;
    for(int i=cntr;i<ones.size();i++){
        a++;
        cout<<ones[cntr++]<<" ";
        if(a==3){a=0;cout<<endl;}
    }
    for(int i=0;i<v.size();i++){
        for(int j=0;j<v[i].size();j++){
            cout<<v[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}
/*


*/