#include <bits/stdc++.h>
const long long N = 1e5 + 7, mod = 998244353, iz = 1 << 21, oz = 1 << 22;
typedef long long aN[N];
char is[iz], *i1 = is, *i2 = is, os[oz], *o1 = os, *o2 = os + oz;
int fgc() {
  return i1 == i2 && is == (i2 = is + fread(i1 = is, 1, iz, stdin)) ? -1
                                                                    : *i1++;
}
void fout() { fwrite(os, o1 - os, 1, stdout), o1 = os; }
int fpc(int c) {
  if (o1 == o2) fout();
  return *o1++ = c;
}
int (*gc)() = getchar, (*pc)(int) = putchar, wt[126];
int readchar(int l = 33, int r = 126) {
  if (l > r) std::swap(l, r);
  int c = gc();
  for (; c < l || c > r; c = gc())
    ;
  return c;
}
long long readll() {
  long long x = 0, w = 1;
  int c = gc();
  for (; c < 48 || c > 57; c = gc()) c - 45 || (w = -w);
  for (; c > 47 && c < 58; c = gc()) x = x * 10 + c - 48;
  return x * w;
}
void writell(long long u, int c = 32) {
  int t = 0;
  for (register unsigned long long n = u < 0 ? pc(45), 0ull - u : u; n; n /= 10)
    wt[++t] = n % 10 ^ 48;
  for (t || pc(48); t;) pc(wt[t--]);
  c&& pc(c);
}
int mygets(char* s, int c = 0) {
  char* t = s + 1;
  while ((*s = gc()) < 33)
    ;
  while ((*t = gc()) > 32) t++;
  c && (*t++ = c), *t = 0;
  return t - s;
}
int myputs(const char* s, int c = 10) {
  const char* t = s;
  while (*t) pc(*t++);
  c&& pc(c);
  return t - s + (c != 0);
}
unsigned long long f[49];
long long ans[6];
void dfs0(long long c, long long S) {
  if (c == 5) {
    for (register long long i = 0; i < 5; i++) writell(ans[i] + 1);
    pc(10);
    exit(0);
  }
  for (register long long i = 0; i < 48; i++)
    if (S >> i & 1) {
      ans[c] = i;
      dfs0(c + 1, S & f[i]);
    }
}
void dfs1(long long c, long long S) {
  if (c == 5) {
    for (register long long i = 0; i < 5; i++) writell(ans[i] + 1);
    pc(10);
    exit(0);
  }
  for (register long long i = 0; i < 48; i++)
    if (S >> i & 1) {
      ans[c] = i;
      dfs1(c + 1, S & ~f[i] & ~(1ull << i));
    }
}
int main() {
  *"" &&
      freopen(
          ""
          ".in",
          "r", stdin) &&
      freopen(
          ""
          ".out",
          "w", stdout),
      gc = fgc, pc = fpc, atexit(fout);
  long long n = std::min(48ll, readll()), m = readll();
  for (register long long i = 1; i <= m; i++) {
    long long u = readll() - 1, v = readll() - 1;
    if (u < n && v < n) f[u] |= 1ull << v, f[v] |= 1ull << u;
  }
  dfs0(0, (1ull << n) - 1), dfs1(0, (1ull << n) - 1);
  myputs("-1");
  return 0;
}

### Prompt

Please create a solution in CPP to the following problem:

On the great island of Baltia, there live N people, numbered from 1 to N. There are exactly M pairs of people that are friends with each other. The people of Baltia want to organize a successful party, but they have very strict rules on what a party is and when the party is successful. On the island of Baltia, a party is a gathering of exactly 5 people. The party is considered to be successful if either all the people at the party are friends with each other (so that they can all talk to each other without having to worry about talking to someone they are not friends with) or no two people at the party are friends with each other (so that everyone can just be on their phones without anyone else bothering them). Please help the people of Baltia organize a successful party or tell them that it's impossible to do so.

Input

The first line contains two integer numbers, N (5 ≤ N ≤ 2*10^5) and M (0 ≤ M ≤ 2*10^5) – the number of people that live in Baltia, and the number of friendships. The next M lines each contains two integers U_i and V_i (1 ≤ U_i,V_i ≤ N) – meaning that person U_i is friends with person V_i. Two friends can not be in the list of friends twice (no pairs are repeated) and a person can be friends with themselves (U_i ≠ V_i).

Output

If it's possible to organize a successful party, print 5 numbers indicating which 5 people should be invited to the party. If it's not possible to organize a successful party, print -1 instead. If there are multiple successful parties possible, print any.

Examples

Input


6 3
1 4
4 2
5 4


Output


1 2 3 5 6


Input


5 4
1 2
2 3
3 4
4 5


Output


-1

### Response

```cpp
#include <bits/stdc++.h>
const long long N = 1e5 + 7, mod = 998244353, iz = 1 << 21, oz = 1 << 22;
typedef long long aN[N];
char is[iz], *i1 = is, *i2 = is, os[oz], *o1 = os, *o2 = os + oz;
int fgc() {
  return i1 == i2 && is == (i2 = is + fread(i1 = is, 1, iz, stdin)) ? -1
                                                                    : *i1++;
}
void fout() { fwrite(os, o1 - os, 1, stdout), o1 = os; }
int fpc(int c) {
  if (o1 == o2) fout();
  return *o1++ = c;
}
int (*gc)() = getchar, (*pc)(int) = putchar, wt[126];
int readchar(int l = 33, int r = 126) {
  if (l > r) std::swap(l, r);
  int c = gc();
  for (; c < l || c > r; c = gc())
    ;
  return c;
}
long long readll() {
  long long x = 0, w = 1;
  int c = gc();
  for (; c < 48 || c > 57; c = gc()) c - 45 || (w = -w);
  for (; c > 47 && c < 58; c = gc()) x = x * 10 + c - 48;
  return x * w;
}
void writell(long long u, int c = 32) {
  int t = 0;
  for (register unsigned long long n = u < 0 ? pc(45), 0ull - u : u; n; n /= 10)
    wt[++t] = n % 10 ^ 48;
  for (t || pc(48); t;) pc(wt[t--]);
  c&& pc(c);
}
int mygets(char* s, int c = 0) {
  char* t = s + 1;
  while ((*s = gc()) < 33)
    ;
  while ((*t = gc()) > 32) t++;
  c && (*t++ = c), *t = 0;
  return t - s;
}
int myputs(const char* s, int c = 10) {
  const char* t = s;
  while (*t) pc(*t++);
  c&& pc(c);
  return t - s + (c != 0);
}
unsigned long long f[49];
long long ans[6];
void dfs0(long long c, long long S) {
  if (c == 5) {
    for (register long long i = 0; i < 5; i++) writell(ans[i] + 1);
    pc(10);
    exit(0);
  }
  for (register long long i = 0; i < 48; i++)
    if (S >> i & 1) {
      ans[c] = i;
      dfs0(c + 1, S & f[i]);
    }
}
void dfs1(long long c, long long S) {
  if (c == 5) {
    for (register long long i = 0; i < 5; i++) writell(ans[i] + 1);
    pc(10);
    exit(0);
  }
  for (register long long i = 0; i < 48; i++)
    if (S >> i & 1) {
      ans[c] = i;
      dfs1(c + 1, S & ~f[i] & ~(1ull << i));
    }
}
int main() {
  *"" &&
      freopen(
          ""
          ".in",
          "r", stdin) &&
      freopen(
          ""
          ".out",
          "w", stdout),
      gc = fgc, pc = fpc, atexit(fout);
  long long n = std::min(48ll, readll()), m = readll();
  for (register long long i = 1; i <= m; i++) {
    long long u = readll() - 1, v = readll() - 1;
    if (u < n && v < n) f[u] |= 1ull << v, f[v] |= 1ull << u;
  }
  dfs0(0, (1ull << n) - 1), dfs1(0, (1ull << n) - 1);
  myputs("-1");
  return 0;
}

```