#include <bits/stdc++.h>

#define FOR(i,n) for(int i=0;i<(n);++i)
#define FORU(i,j,k) for(int i=(j);i<=(k);++i)
#define FORD(i,j,k) for(int i=(j);i>=(k);--i)

#define X(a) get<0>(a)
#define Y(a) get<1>(a)
#define Z(a) get<2>(a)
#define W(a) get<3>(a)

#define all(x) begin(x),end(x)
#define pb push_back
#define mt make_tuple
#define mp make_pair

using namespace std;
using vi = vector<int>;
using pii = pair<int,int>;
using vvi = vector<vi>;
using vii = vector<pii>;
using vvii = vector<vii>;

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

struct WLGIso {
  vvi G[2];
  int n;
  vi  ghashes;

  int partitionSize = 0;
  vvi partition[2];
  vi  color[2];
  vi  hash[2];

  vi inQ;
  vi Q;

  vector<tuple<int, vector<tuple<int,array<vi,2>>>>> history;

  WLGIso(vvi G1, vvi G2) {
    G[0] = G1; G[1] = G2;
    n = G1.size();
    assert(n == (int)G2.size());
    ghashes.resize(2*n);
    FOR(i,2*n) ghashes[i] = rand()*rand()+rand();
    FOR(ix,2) {
      color[ix].resize(n);
      hash[ix].assign(n,0ll);
    }
    // Initialize the partition
    { unordered_map<int, array<vi,2>> dPartition;
      FOR(ix,2) FOR(i,n) dPartition[G[ix][i].size()][ix].pb(i);
      for(auto const& p : dPartition) {
        array<vi,2> const& v = p.second;
        assert(v[0].size() == v[1].size());
        FOR(ix,2) {
          partition[ix].emplace_back();
          for(int i : v[ix]) {
            partition[ix].back().pb(i);
            color[ix][i] = partitionSize;
          }
        }
        inQ.pb(1); Q.pb(partitionSize); partitionSize++;
      }
    }
    // Initialize the hashes
    FOR(ix,2) FOR(i,n) for(int j : G[ix][i]) {
      hash[ix][i] += ghashes[color[ix][j]];
    }

    history.emplace_back(); X(history.back()) = partitionSize;
  }

  void push(int i) {
    if(partition[0][i].size() > 1 && !inQ[i]) {
      inQ[i]=1;
      Q.pb(i);
    }
  }

  void split(int i, vector<array<vi,2>> const& w){
    Y(history.back()).emplace_back(i,array<vi,2>{{partition[0][i],partition[1][i]}});
    FOR(ix,2) for(int j : partition[ix][i]) for(int k : G[ix][j]) {
        push(color[ix][k]);
        hash[ix][k] -= ghashes[i];
      }
    bool first = 1;
    for(auto const& v : w) {
      int pi = first ? i : partitionSize;
      if(!first) {
        FOR(ix,2) partition[ix].emplace_back();
        inQ.pb(0);
        partitionSize += 1;
      }else{
        FOR(ix,2) partition[ix][pi].clear();
      }
      first = 0;

      FOR(ix,2) for(int j : v[ix]) {
        partition[ix][pi].pb(j);
        color[ix][j] = pi;
        for(int k : G[ix][j]) {
          hash[ix][k] += ghashes[pi];
        }
      }
      push(pi);
    }
  }

  bool refine(){
    while(!Q.empty()) {
      int i = Q.back(); Q.pop_back(); inQ[i]=0;
      unordered_map<int, array<vi,2> > hPart;
      FOR(ix,2) for(int j : partition[ix][i]) {
        hPart[hash[ix][j]][ix].pb(j);
      }
      for(auto const& q : hPart) {
        auto const& v = q.second;
        if(v[0].size() != v[1].size()) return false;
      }
      if(hPart.size() == 1) continue;
      vector<array<vi,2>> w;
      for(auto const& q : hPart) w.pb(q.second);
      split(i,w);
    }
    return true;
  }

  void backtrack() {
    int oldSize = X(history.back());
    vector<tuple<int,array<vi,2>>>& v = Y(history.back());
    FOR(ix,2) while((int)partition[ix].size() > oldSize) {
      int pi = partition[ix].size() - 1;
      for(int i : partition[ix].back()) for(int j : G[ix][i]) {
          hash[ix][j] -= ghashes[pi];
      }
      partition[ix].pop_back();
    }
    while(!v.empty()) {
      int i = X(v.back());
      array<vi,2> const& w = Y(v.back());
      if(i<oldSize) {
        FOR(ix,2) {
          for(int j : partition[ix][i]) for(int k : G[ix][j]) {
              hash[ix][k] -= ghashes[i];
            }
          partition[ix][i] = w[ix];
          for(int j : partition[ix][i]) {
            color[ix][j] = i;
            for(int k : G[ix][j]) {
              hash[ix][k] += ghashes[i];
            }
          }
        }
      }
      v.pop_back();
    }
    partitionSize = oldSize;
    inQ.resize(oldSize);
    history.pop_back();
  }

  bool run(int i){
    history.emplace_back(); X(history.back()) = partitionSize;
    if(!refine()) {
      backtrack();
      return 0;
    }

    while(i<partitionSize && partition[0][i].size() == 1) {
      i++;
    }
    if(i == partitionSize) return 1;

    FOR(j, (int)partition[1][i].size()) {
      history.emplace_back(); X(history.back()) = partitionSize;

      vector<array<vi,2>> w(2);
      FOR(ix,2) w[0][ix] = partition[ix][i];
      swap(w[0][1][j],w[0][1].back());
      FOR(ix,2) {
        w[1][ix].pb(w[0][ix].back());
        w[0][ix].pop_back();
      }

      split(i, w);
      if(run(i)) return 1;
      backtrack();
    }

    backtrack();
    return 0;
  }
};

int main(){
  cin.tie(0); ios::sync_with_stdio(0);

  int n,m; cin>>n>>m;
  vvi G(n);
  FOR(i,m) {
    int u,v; cin>>u>>v;
    --u; --v;
    G[u].pb(v);
    G[v].pb(u);
  }

  int hm=0;
  vvi H(n);
  FORU(i,1,n) for(int k=2; k*i<=n; ++k) {
    hm++;
    H[i-1].pb(i*k-1);
    H[i*k-1].pb(i-1);
  }
  assert(m==hm);

  WLGIso w(G,H);
  bool ok = w.run(0);
  assert(ok);
  vi ans(n);
  FOR(i,n) {
    ans[w.partition[0][i][0]] = w.partition[1][i][0]+1;
  }
  FOR(i,n) {
    cout << ans[i] << ' ';
  }
  cout << endl;

  return 0;
}