这道题,我独自写实在太恶心太困难了,很难写出来这样长的模拟,所以为了节省时间(偷懒),我们可以看看官方题解怎么写的,进步从模仿开始,照着官方的题解一个一个子敲完之后,我把大家可能看不懂的地方,进行了一定的注释,尽量能让大家读懂代码某些地方是为了干什么的,当然我只是个小菜鸡,肯定有理解不到位的地方也请多多包涵

然后官方代码写的很好,但有一些地方是有冗余或者不太需要的变量或者建边,在我这里已经删除了,我这个代码肯定是能通过的,因为验证过(除非数据太水,你也可以试试看hack我)

最后建议大家有能力的看完可以独立敲敲,有点懒的可以跟着敲敲,看懂是一种,但敲的时候才能体会到一些细节处理很妙

#define pb push_back
#define vt vector
#define fi first
#define se second
int n,m;
void solve(){
	cin >> n >> m;
	vt<vt<int>> vx(n + 1),vy = vx; //水平线,垂直线
	vt<vt<PII>> vr(n + 1); //环形道路
	map<PII,int> id; //每个(x,y)的换乘点的编号
	vt<PII> node(m + 3); //m个换乘点+起点终点
	for(int i = 1;i <= m + 2;i++){
		int x,y;
		cin >> x >> y;
		PII p = {x,y};
		if(i > 2 && p==node[1]) continue; //起点换乘,我一开始不走到后面再换乘肯定不优
		if(i > 2 && p==node[2]) continue; //终点换乘,都到终点了为什么换乘呢??
		vx[x].pb(y); //x这个轴上有y这个点
		vy[y].pb(x); //y这个轴上有x这个点
		int r = min({x,n-x+1,y,n-y+1}); //根据题意推出
		vr[r].pb({x,y}); //环形上有{x,y}这个点
		id[{x,y}] = i;
		node[i] = {x,y};
	}
	//到此第一部分结束,该部分主要将每个换乘点存在不同的铁路航向数组里,并且把点和编号映射起来一一对应
	int sz = (m + 3) * 3; //点集大小,因为一个点拆成三个方向,所以有(m + 2)*3个点,防止越界就(m+3)*3
	vt<vt<PII>> e(sz); //常规邻接表 {邻点,边权}
	//第一个点拆成 3,4,5 第二个点 6,7,8 以此类推
	for(int i = 1;i <= m + 2;i++){ 
		e[i * 3].pb({i * 3 + 1,1}); //换乘时间为1
		e[i * 3].pb({i * 3 + 2,1});
		e[i * 3 + 1].pb({i * 3,1});
		e[i * 3 + 1].pb({i * 3 + 2,1});		
		e[i * 3 + 2].pb({i * 3 + 1,1});
		e[i * 3 + 2].pb({i * 3,1});		
	}
	auto get = [&](PII pr)->int{
		auto &[x,y] = pr;
		int l = min({x,n-x+1,y,n-y+1});
		int ans = 0;
		int r = n - l + 1; //左边界右边界
		int len = r - l; //长度
		//下面是最复杂的一段,可以理解为从环形左上角做顺时针运动到x,y点需要移动多少距离
		//我们求了x1,y1点距离后,再求x2,y2点距离,作差就可以得到这两个点顺时针移动的 相距距离
		if(x==l){
			ans += y - l;
		}else if(y==r){
			ans += len + x - l;
		}else if(x==r){
			ans += len*2 + r - y; 
		}else{
			ans += len * 3 + r - x;
		}
		return ans;
	};
	auto link = [&](int x1,int y1,int x2,int y2,int t)->void{
		int u = id[{x1,y1}] * 3 + t; //点的组成->点和当前铁轨类型
		int v = id[{x2,y2}] * 3 + t; //点的组成->点和当前铁轨类型
		int d = 1e9;
		if(t!=2){ //0,1是普通铁轨,很好处理
			d = (abs(x1 - x2) + abs(y1 - y2)) * 2;
		}else{
			int d0 = get({x1,y1}); 
			int d1 = get({x2,y2});
			int l = min({x1,n-x1+1,y1,n-y1+1});
			int r = n - l + 1;
			int len = r- l;
			int M = len * 4; //总长度
			d = min((d0 - d1 + M)%M,(d1 - d0 + M)%M) * 2; //顺时针或者逆时针的最小值
		}
		e[u].pb({v,d});
		e[v].pb({u,d});
	};
	for(int i = 1;i <= n;i++){
		sort(all(vx[i])); //我这里的all就是 begin,end
		sort(all(vy[i]));
		sort(all(vr[i]),[&](PII x1,PII x2){return get(x1) < get(x2);});
		for(int j = 0;j < vx[i].size();j++){
			if(j > 0) link(i,vx[i][j],i,vx[i][j - 1],0);
		}
		for(int j = 0;j < vy[i].size();j++){
			if(j > 0) link(vy[i][j],i,vy[i][j - 1],i,1);
		}
		if(vr[i].size()){
			auto &v = vr[i];
			int M = v.size();
			for(int j = 0;j < M;j++){
				int f = (j - 1 + M)%M; //首尾都要连因为是环形
				link(v[j].fi,v[j].se,v[f].fi,v[f].se,2);
			}
		}
	}
	vt<int> dis(sz,1e9),vis(sz),pre(sz);
	dis[3] = 0;
	dis[4] = 0;
	dis[5] = 0;
	set<PII> h; //用set实现小根堆,下面就是常规最短路操作
	h.insert({0,3});
	h.insert({0,4});
	h.insert({0,5});
	while(h.size()){
		auto [d,u] = *h.begin();
		h.erase(h.begin());
		if(vis[u]) continue;
		vis[u] = 1;
		for(auto &[v,w]:e[u]){
			if(dis[v] < dis[u]+w) continue;
			dis[v] = dis[u] + w;
			pre[v] = u;
			h.insert({dis[v],v});
		}
	}
	PII ans = {1e9,1e9};
	auto &[x,y] = ans;
	ans = min(ans,{dis[6],6}); //终点距离,编号
	ans = min(ans,{dis[7],7});
	ans = min(ans,{dis[8],8});
	if(x >= 1e9){
		cout << "Impossible!" << endl;
	}else{
		cout << x << endl;
		vt<array<int,3>> v;
		for(int i = y;i;i = pre[i]){
			v.pb({node[i/3].fi,node[i/3].se,i%3}); //直接用编号可得(x,y),铁轨类型
		}
		reverse(all(v));
		vt<PII> ans;
		string s;
		string p = "RCO"; //三种类型的铁轨,向左右,向上下,环形
		for(auto &[x,y,t]:v){
			ans.pb({x,y});
			PII tp = {x,y};
			if(tp!=node[2]){
				s+=p[t]; 
			}
			while(s.size() >= 2 && s.back() == s[s.size() - 2]){ //同类型铁轨不用换乘,直接一路删就行了
				s.pop_back();
				ans.pop_back();
			}
		}
		cout << s.size() << endl;
		for(int i = 0; i < ans.size();i++){
			cout << ans[i].fi << " " << ans[i].se << endl;
			if(i + 1 < ans.size()){ //根据现在两个点位置判断方向,因为铁轨类型已经确定,现在只要确定方向
				char ch = '#';
				if(s[i]=='R'){
					if(ans[i + 1].se > ans[i].se){
						ch = 'E';
					}else{
						ch = 'W';
					}
				}
				if(s[i]=='C'){
					if(ans[i + 1].fi > ans[i].fi){
						ch = 'S';
					}else{
						ch = 'N';
					}
				}
				if(s[i]=='O'){
					int d0 = get(ans[i]); 
					int d1 = get(ans[i+1]);
					int l = min({ans[i].fi,n-ans[i].fi+1,ans[i].se,n-ans[i].se+1});
					int r = n - l + 1;
					int len = r- l;
					int M = len * 4;
					if((d0 - d1 + M)%M < (d1 - d0 + M)%M){ //这里和题解写的不一样,本质就是最上面get方法里面的比大小
						ch = 'I';
					}else{
						ch = 'C';
					}
				}
				cout << ch << endl;
			}
			
		}
	}
}

signed main(){
	std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
	int times = 1;
	//cin >> times;
	while(times--){
		solve();
	}
	return 0;
}