Shared code

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(ll i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define F first
#define S second
#define pb push_back
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

bool has(vi& v, int x){
	int j = lower_bound(all(v),x)-v.begin();
	return j<sz(v) && v[j] == x;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	int n,m;cin>>n>>m;
	vector<vi> adj(n+2);
	rep(i,0,n+1)adj[i].pb(n+1);
	rep(i,0,n)adj[n].pb(i);
	rep(_,0,m){
		int a,b;cin>>a>>b;a--;b--;
		adj[a].pb(b);
	}
	rep(i,0,n+2)sort(all(adj[i]));
	vi id(n+2,0);
	rep(i,0,n+2) for(int x : adj[i]) id[x]++;
	vi o;
	rep(i,0,n+2)if(id[i]==0)o.pb(i);
	rep(j,0,n+2) for(int con : adj[o[j]]) if(--id[con] ==0) o.pb(con);
	vi r(n+2);rep(i,0,n+2)r[o[i]]=i;
	vi ps(n+2,0);
	rep(i,0,n+1)ps[i+1]=ps[i]+has(adj[o[i]],o[i+1]);
	vi nex(n+2,-2);
	nex[n]=-1;
	for(int i = n-1; i>=0; i--){
		int x = o[i];
		for(int y : adj[x])if(r[y]>i+1 && nex[r[y]-1]!=-2 && ps[r[y]-1]-ps[i+1]==(r[y]-2-i)) nex[i]=r[y]-1;
	}
	int loc = 0;
	if(nex[loc]==-2){
		cout<<"NO\n";
		return 0;
	}
	vi toggles={0};
	while(true){
		toggles.pb(loc+1);
		if(nex[loc]==-1) break;
		loc=nex[loc];
	}
	vi ans(n+2,0);
	rep(i,1,sz(toggles))rep(j,toggles[i-1],toggles[i]) ans[j]=i%2;
	vector<vi> paths(2);
	rep(i,1,n+1) paths[ans[i]].pb(o[i]);
	cout<<"YES\n";
	rep(i,0,2){
		cout<<sz(paths[i]);
		for(int x : paths[i])cout<<' '<<x+1;
		cout<<'\n';
	}
}