一道简单构造题。
如果 \(m=\frac{n(n-1)}{2}\)，此时任意两个数都要有偏序关系，但是又要求第二个数列有两个数相等，因此无解。
否则一定有解。不难想到构造两个数列使它们几乎完全相等。可以找到两个没有偏序关系的下标 \((i,j)\)，在第一个数列中分别赋值为 \(n-1,n\)，在第二个数列中均赋值为 \(n-1\)。剩下的数随便填，让两个数列对应位置相等即可。
// Problem: CF1090D Similar Arrays
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1090D
// Memory Limit: 500 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
#define likely(exp) __builtin_expect(!!(exp), 1)
#define unlikely(exp) __builtin_expect(!!(exp), 0)
using namespace std;
typedef long long ll;
mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
uniform_int_distribution<int> dist(L, R);
return dist(rnd);
}
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
const int N = 1e5+5;
int n, m, vis[N], a[N];
vector<int> e[N];
int main() {
scanf("%d%d", &n, &m);
rep(i, 1, m) {
int u, v;
scanf("%d%d", &u, &v);
e[u].push_back(v);
e[v].push_back(u);
}
if(m == n * (n - 1) / 2) return puts("NO")&0;
int pa = -1, pb = -1, now = 0;
rep(i, 1, n) {
if((int)e[i].size() == n - 1) continue;
for(int j : e[i]) vis[j] = 1;
rep(j, 1, n) if(i != j && !vis[j]) {pa = i; pb = j; break;}
break;
}
rep(i, 1, n) if(i != pa && i != pb) a[i] = ++now;
a[pa] = n - 1; a[pb] = n;
puts("YES");
rep(i, 1, n) printf("%d%c", a[i], " \n"[i==n]);
rep(i, 1, n) printf("%d%c", min(a[i], n-1), " \n"[i==n]);
return 0;
}