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 JAVA):

Solution:
import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.*;

public class P300B {

String binStr(long val) { String ret = Long.toBinaryString(val); while (ret.length() < n) { ret = ("0" + ret); } return ret; }
void displayTeams() {
  for (int i = 1; i <= 3; i++) {
    print("[Team (" + i + "): "); teams[i].stream().forEach(x -> print(binStr(x) + ", ")); println("\b\b]");
  }
  pw.flush();
}

  @SuppressWarnings("unchecked")
  Set<Long> [] teams = new HashSet [4];
  int n, m;

  long stud2team(int s) {
    return (1L << (s - 1));
  }

  ArrayList<Integer> team2stud(long team) {
    ArrayList<Integer> studs = new ArrayList<Integer>();
    for (int i = 1; ((studs.size() < 3) && (i <= n)); i++) {
      if ((team & stud2team(i)) != 0) {
        studs.add(i);
      }
    }
    return studs;
  }

  int bc(long l) {
    return Long.bitCount(l);
  }

  long getTeam(int count) { // get team by studens count
    return ((teams[count].size() != 0) ? teams[count].iterator().next() : (-1));
  }

  long getTeam(long stud) { // get team by student
    for (Set<Long> team : teams) {
      for (long subteam : team) {
        if ((subteam & stud) != 0) {
          return subteam;
        }
      }
    }
    return 0;
  }
  
  boolean addTeam(long team) {
    if ((bc(team) >= 1) && (bc(team) <= 3)) {
      teams[bc(team)].add(team);
      return true;
    }
    return false;
  }

  void remTeam(long team) {
    teams[bc(team)].remove(team);
  }

  public void run() throws Exception {
    n = nextInt();
    m = nextInt();
    Arrays.asList(0, 1, 2, 3).parallelStream().forEach(idx -> { teams[idx] = new HashSet<Long>(); });
    
    for (int i = 1; i <= n; i++) {
      addTeam(stud2team(i));
    }

    while ((m--) > 0) {
      long t1 = getTeam(stud2team(nextInt()));
      long t2 = getTeam(stud2team(nextInt()));
      remTeam(t1);
      remTeam(t2);
      if (!addTeam(t1 | t2)) {
        println(-1);
        return;
      }
    }

    boolean teamsChanged = true;
    while (teamsChanged) {
      teamsChanged = false;

      if ((teams[2].size() > 0) && (teams[1].size() > 0)) { // searching teams with 2 and 1 students
        long t1 = getTeam(1);
        remTeam(t1);
        long t2 = getTeam(2);
        remTeam(t2);
        addTeam(t1 | t2);
        teamsChanged = true;
      } else if (teams[1].size() > 1) { // searching 2 teams with 1 students
        long t1 = getTeam(1);
        remTeam(t1);
        long t2 = getTeam(1);
        remTeam(t2);
        addTeam(t1 | t2);
        teamsChanged = true;
      }
    }

    if (teams[3].size() != (n / 3)) {
      println(-1);
      return;
    }

    teams[3].stream()
            .forEach(team -> { team2stud(team).stream()
                                              .forEach(stud -> print(stud + " ")); println(); });
  }

  public static void main(String... args) throws Exception {
    br = new BufferedReader(new InputStreamReader(System.in));
    pw = new PrintWriter(new BufferedOutputStream(System.out));
    new P300B().run();
    br.close();
    pw.close();
  }

  static BufferedReader br;
  static PrintWriter pw;
  StringTokenizer stok;

  String nextToken() throws IOException {
    while (stok == null || !stok.hasMoreTokens()) {
      String s = br.readLine();
      if (s == null) { return null; }
      stok = new StringTokenizer(s);
    }
    return stok.nextToken();
  }

  void print(byte b) { print("" + b); }
  void print(int i) { print("" + i); }
  void print(long l) { print("" + l); }
  void print(double d) { print("" + d); }
  void print(char c) { print("" + c); }
  void print(Object o) {
    if (o instanceof int[]) { print(Arrays.toString((int [])o));
    } else if (o instanceof long[]) { print(Arrays.toString((long [])o));
    } else if (o instanceof char[]) { print(Arrays.toString((char [])o));
    } else if (o instanceof byte[]) { print(Arrays.toString((byte [])o));
    } else if (o instanceof short[]) { print(Arrays.toString((short [])o));
    } else if (o instanceof boolean[]) { print(Arrays.toString((boolean [])o));
    } else if (o instanceof float[]) { print(Arrays.toString((float [])o));
    } else if (o instanceof double[]) { print(Arrays.toString((double [])o));
    } else if (o instanceof Object[]) { print(Arrays.toString((Object [])o));
    } else { println("" + o); }
  }
  void print(String s) { pw.print(s); }
  void println() { println(""); }
  void println(byte b) { println("" + b); }
  void println(int i) { println("" + i); }
  void println(long l) { println("" + l); }
  void println(double d) { println("" + d); }
  void println(char c) { println("" + c); }
  void println(Object o) { print(o); println(); }
  void println(String s) { pw.println(s); }
  int nextInt() throws IOException { return Integer.parseInt(nextToken()); }
  long nextLong() throws IOException { return Long.parseLong(nextToken()); }
  double nextDouble() throws IOException { return Double.parseDouble(nextToken()); }
  char nextChar() throws IOException { return (char) (br.read()); }
  String next() throws IOException { return nextToken(); }
  String nextLine() throws IOException { return br.readLine(); }
  int [] readInt(int size) throws IOException {
    int [] array = new int [size];
    for (int i = 0; i < size; i++) { array[i] = nextInt(); }
    return array;
  }
  long [] readLong(int size) throws IOException {
    long [] array = new long [size];
    for (int i = 0; i < size; i++) { array[i] = nextLong(); }
    return array;
  }
  double [] readDouble(int size) throws IOException {
    double [] array = new double [size];
    for (int i = 0; i < size; i++) { array[i] = nextDouble(); }
    return array;
  }
  String [] readLines(int size) throws IOException {
    String [] array = new String [size];
    for (int i = 0; i < size; i++) { array[i] = nextLine(); }
    return array;
  }
}