Problem: A famous sculptor Cicasso goes to a world tour!

Well, it is not actually a world-wide. But not everyone should have the opportunity to see works of sculptor, shouldn't he? Otherwise there will be no any exclusivity. So Cicasso will entirely hold the world tour in his native country — Berland.

Cicasso is very devoted to his work and he wants to be distracted as little as possible. Therefore he will visit only four cities. These cities will be different, so no one could think that he has "favourites". Of course, to save money, he will chose the shortest paths between these cities. But as you have probably guessed, Cicasso is a weird person. Although he doesn't like to organize exhibitions, he likes to travel around the country and enjoy its scenery. So he wants the total distance which he will travel to be as large as possible. However, the sculptor is bad in planning, so he asks you for help. 

There are n cities and m one-way roads in Berland. You have to choose four different cities, which Cicasso will visit and also determine the order in which he will visit them. So that the total distance he will travel, if he visits cities in your order, starting from the first city in your list, and ending in the last, choosing each time the shortest route between a pair of cities — will be the largest. 

Note that intermediate routes may pass through the cities, which are assigned to the tour, as well as pass twice through the same city. For example, the tour can look like that: <image>. Four cities in the order of visiting marked as overlines: [1, 5, 2, 4].

Note that Berland is a high-tech country. So using nanotechnologies all roads were altered so that they have the same length. For the same reason moving using regular cars is not very popular in the country, and it can happen that there are such pairs of cities, one of which generally can not be reached by car from the other one. However, Cicasso is very conservative and cannot travel without the car. Choose cities so that the sculptor can make the tour using only the automobile. It is guaranteed that it is always possible to do. 

Input

In the first line there is a pair of integers n and m (4 ≤ n ≤ 3000, 3 ≤ m ≤ 5000) — a number of cities and one-way roads in Berland.

Each of the next m lines contains a pair of integers ui, vi (1 ≤ ui, vi ≤ n) — a one-way road from the city ui to the city vi. Note that ui and vi are not required to be distinct. Moreover, it can be several one-way roads between the same pair of cities. 

Output

Print four integers — numbers of cities which Cicasso will visit according to optimal choice of the route. Numbers of cities should be printed in the order that Cicasso will visit them. If there are multiple solutions, print any of them.

Example

Input

8 9
1 2
2 3
3 4
4 1
4 5
5 6
6 7
7 8
8 5


Output

2 1 8 7

Note

Let d(x, y) be the shortest distance between cities x and y. Then in the example d(2, 1) = 3, d(1, 8) = 7, d(8, 7) = 3. The total distance equals 13. 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline T SQR(T x) {
  return x * x;
}
template <typename T>
inline T MIN(T x, T y) {
  return (x < y) ? x : y;
}
template <typename T>
inline T MAX(T x, T y) {
  return (x > y) ? x : y;
}
template <typename T>
inline T ABS(T x) {
  return (x > 0) ? x : -x;
}
template <typename T>
inline void UPDATE_MIN(T &x, T y) {
  if (y < x) {
    x = y;
  }
}
template <typename T>
inline void UPDATE_MAX(T &x, T y) {
  if (x < y) {
    x = y;
  }
}
template <typename T>
inline int ARGMAX(T cont) {
  return max_element(cont.begin(), cont.end()) - cont.begin();
}
template <typename T>
inline int ARGMIN(T cont) {
  return min_element(cont.begin(), cont.end()) - cont.begin();
}
vector<string> split(const string &s, char c) {
  vector<string> v;
  stringstream ss(s);
  string x;
  while (getline(ss, x, c)) v.emplace_back(x);
  return move(v);
}
template <typename T, typename... Args>
inline string arrStr(T arr, int n) {
  stringstream s;
  s << "[";
  for (__typeof(n - 1) i = (0), __tmpvar__end87 = (n - 1); i < __tmpvar__end87;
       i++)
    s << arr[i] << ",";
  s << arr[n - 1] << "]";
  return s.str();
}
template <class T>
inline string TOSTR(const T &x) {
  stringstream ss;
  ss << x;
  return ss.str();
}
inline void PR(void) {}
inline void PR(int x) { printf("%d", x); }
inline void PR(long long x) { printf("%lld", x); }
inline void PR(char *s) { printf("%s", s); }
inline void PR(const char *s) { printf("%s", s); }
inline void PR(double f) { printf("%.10lf", f); }
inline void PR(long double f) { printf("%.10llf", f); }
inline void PR(vector<int> &vec) {
  for (auto x : vec) {
    PR(x);
    putc(0x20, stdout);
  }
}
template <typename T>
inline void PRS(T x) {
  PR(x);
  putc(0x20, stdout);
}
template <typename T>
inline void PRN(T x) {
  PR(x);
  putc(0x0a, stdout);
}
void PRN(void) { putc(0x0a, stdout); }
inline int gcd(int a, int b) { return a ? gcd(b % a, a) : b; }
inline long long gcd(long long a, long long b) { return a ? gcd(b % a, a) : b; }
inline long long powmod(long long a, long long p, long long m) {
  long long r = 1;
  while (p) {
    if (p & 1) r = r * a % m;
    p >>= 1;
    a = a * a % m;
  }
  return r;
}
struct pairhash {
  template <typename T, typename U>
  std::size_t operator()(const std::pair<T, U> &x) const {
    return std::hash<T>()(x.first) ^ std::hash<U>()(x.second);
  }
};
template <typename K, typename V>
V GetWithDef(const std::map<K, V> &m, const K &key, const V &defval) {
  auto it = m.find(key);
  return (it == m.end()) ? defval : it->second;
}
template <typename K, typename V>
void SetDef(std::map<K, V> &m, const K &key, const V &defval) {
  auto it = m.find(key);
  if (it == m.end()) m[key] = defval;
}
template <typename K, typename V>
V GetWithDef(const std::unordered_map<K, V> &m, const K &key, const V &defval) {
  auto it = m.find(key);
  return (it == m.end()) ? defval : it->second;
}
template <typename K, typename V>
void SetDef(std::unordered_map<K, V> &m, const K &key, const V &defval) {
  auto it = m.find(key);
  if (it == m.end()) m[key] = defval;
}
const int MOD = 1000 * 1000 * 1000 + 7;
const double PI = 3.1415926535897932384626433832795l;
inline void addto(int &a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
}
inline int add(int a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
  return a;
}
inline void subto(int &a, int b) {
  a -= b;
  if (a < 0) a += MOD;
  if (a >= MOD) a -= MOD;
}
inline int sub(int a, int b) {
  a -= b;
  if (a < 0) a += MOD;
  if (a >= MOD) a -= MOD;
  return a;
}
inline void multo(int &a, int b) { a = (long long)a * b % MOD; }
inline int mul(int a, int b) { return (long long)a * b % MOD; }
inline int mulmod(int a, int b, int mod) { return (long long)a * b % mod; }
inline int powmod(int a, int e, int mod) {
  int x;
  for (x = 1; e > 0; e >>= 1) {
    if (e & 1) x = mulmod(x, a, mod);
    a = mulmod(a, a, mod);
  }
  return x;
}
inline int invmod_prime(int a, int mod) { return powmod(a, mod - 2, mod); }
inline long long invmod_LL(long long p) {
  long long q = p;
  for (long long a = p * p; a != 1; a *= a) q *= a;
  return q;
}
int N, M, K, L, E, Q;
vector<int> edges[10123];
vector<int> longest[10123];
vector<int> shortest_path[10123];
vector<int> back_edges[10123];
vector<int> back_longest[10123];
vector<int> back_shortest_path[10123];
void bfs(int i) {
  vector<char> visited(N, 0);
  shortest_path[i].assign(N, -1);
  shortest_path[i][i] = 0;
  deque<int> q = {i};
  while (q.size()) {
    int s = q.front();
    q.pop_front();
    for (auto &t : edges[s]) {
      if (visited[t]) continue;
      visited[t] = 1;
      shortest_path[i][t] = shortest_path[i][s] + 1;
      longest[i].push_back(t);
      q.push_back(t);
    }
  }
}
void bfs_back(int i) {
  vector<char> visited(N, 0);
  back_shortest_path[i].assign(N, -1);
  back_shortest_path[i][i] = 0;
  deque<int> q = {i};
  while (q.size()) {
    int s = q.front();
    q.pop_front();
    for (auto &t : back_edges[s]) {
      if (visited[t]) continue;
      visited[t] = 1;
      back_shortest_path[i][t] = back_shortest_path[i][s] + 1;
      back_longest[i].push_back(t);
      q.push_back(t);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  set<pair<int, int>> seen;
  scanf("%d%d", &N, &E);
  for (__typeof(E) i = (0), __tmpvar__end287 = (E); i < __tmpvar__end287; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--;
    b--;
    if (a == b) continue;
    pair<int, int> ab = make_pair(a, b);
    edges[a].push_back(b);
    back_edges[b].push_back(a);
  }
  for (__typeof(N) i = (0), __tmpvar__end301 = (N); i < __tmpvar__end301; i++) {
    bfs(i);
    bfs_back(i);
  }
  int ans = -1;
  int ans_p = -1, ans_q = -1, ans_b = -1, ans_s = -1;
  for (__typeof(N) s = (0), __tmpvar__end307 = (N); s < __tmpvar__end307; s++) {
    for (__typeof(N) p = (0), __tmpvar__end308 = (N); p < __tmpvar__end308;
         p++) {
      if (s == p) continue;
      if (shortest_path[s][p] <= 0) continue;
      int b0 = MAX(0, (int)back_longest[s].size() - 4);
      int b1 = back_longest[s].size();
      for (__typeof(b1) bi = (b1)-1, __tmpvar__end313 = (b0);
           bi >= __tmpvar__end313; bi--) {
        int b = back_longest[s][bi];
        if (b == s || b == p) continue;
        if (shortest_path[b][s] <= 0) continue;
        int q0 = MAX(0, (int)longest[p].size() - 4);
        int q1 = longest[p].size();
        for (__typeof(q1) qi = (q1)-1, __tmpvar__end319 = (q0);
             qi >= __tmpvar__end319; qi--) {
          int q = longest[p][qi];
          if (q == b || q == s || q == p) continue;
          if (shortest_path[p][q] <= 0) continue;
          int curlen = 0;
          curlen += shortest_path[b][s];
          curlen += shortest_path[s][p];
          curlen += shortest_path[p][q];
          if (curlen > ans) {
            ans = curlen;
            ans_b = b;
            ans_s = s;
            ans_p = p;
            ans_q = q;
          }
        }
      }
    }
  }
  1;
  PRS(ans_b + 1);
  PRS(ans_s + 1);
  PRS(ans_p + 1);
  PRS(ans_q + 1);
  PRN();
  return 0;
}