由于代码能力拙计，一直很想写这题，于是学了上下界网络流之后就开始写这题了。

感觉理清了思路没有想象中难写。但是感觉要在考场上面写出来确实比较厉害。。

首先第一问DP做法显然。第二问下界最小流有特殊的建图方式然后跑两遍Dinic就好了。。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
#define N 50050
#define M 2000050
#define INF 0x3f7f7f7f
int sg[N],wz[N][2],dir[N][3],fi[N],c[M*2][3],Trs[N];
int ss=1,st,n,m,S=N-1,T=N-2,_S=N-3,_T=N-4,ans;
int Ans[N],cur[N],Wz[N][2],sign[N],ma[N],la[N],h[N];
queue <int> li;bool b[N],flag[N],vis[N];
inline int Read()
 {
 	int x=0;char y;bool z=0;
 	do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
 	do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
 	return z?-x:x;
 }
inline void Line(int x,int y,int z)
 {
 	c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;
 	c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=0;fi[y]=ss;
 }
inline bool cmp0(int x,int y)
 {return wz[x][0]<wz[y][0]||(wz[x][0]==wz[y][0]&&wz[x][1]<wz[y][1]);}
inline bool cmp1(int x,int y)
 {return Wz[x][0]<Wz[y][0]||(Wz[x][0]==Wz[y][0]&&wz[x][1]<wz[y][1]);}
inline bool cmp2(int x,int y)
 {return Wz[x][1]<Wz[y][1]||(Wz[x][1]==Wz[y][1]&&wz[x][1]<wz[y][1]);}
inline bool cmp(int x,int y)
 {return wz[x][1]>wz[y][1]||(wz[x][1]==wz[y][1]&&wz[x][0]<wz[y][0]);}
void Up(int x)
 {
 	if (!x) return;
 	if (x!=n) printf("%d ",x);
 	if (!la[x]) Up(dir[x][Trs[x]]); else
 	 {
 	 	int k=sign[x],l=sign[la[x]],e;
 	 	if (k<l)
 	 	 {
 	 	 	e=k;
 	 	 	while (k-1&&wz[sg[k-1]][1]==wz[sg[k]][1])
 	 	 	  printf("%d ",sg[--k]);
 	 	 	k=e+1;
 	 	 	for (;k<=l;k++) printf("%d ",sg[k]);
 	 	 } else
 	 	 {
 	 	 	e=k;
 	 	 	while (k<n&&wz[sg[k+1]][1]==wz[sg[k]][1])
 	 	 	  printf("%d ",sg[++k]);
 	 	 	k=e-1;
 	 	 	for (;k>=l;k--) printf("%d ",sg[k]);
 	 	 }
 	 	Up(dir[la[x]][Trs[la[x]]]);
 	 }
 	return;
 }
void DP()
 {
 	for (int i=1;i<=n;i++)
 	  Wz[i][0]=wz[i][0]+wz[i][1],
 	  Wz[i][1]=wz[i][0]-wz[i][1];
 	sort(sg+1,sg+n+1,cmp0);
 	for (int i=1;i<=n;i++)
 	 while (i<n&&wz[sg[i+1]][0]==wz[sg[i]][0])
 	   i++,dir[sg[i-1]][1]=sg[i];
 	sort(sg+1,sg+n+1,cmp1);
 	for (int i=1;i<=n;i++)
 	 while (i<n&&Wz[sg[i+1]][0]==Wz[sg[i]][0])
 	   i++,dir[sg[i-1]][0]=sg[i];
 	sort(sg+1,sg+n+1,cmp2);
 	for (int i=1;i<=n;i++)
 	 while (i<n&&Wz[sg[i+1]][1]==Wz[sg[i]][1])
 	   i++,dir[sg[i-1]][2]=sg[i];
 	sort(sg+1,sg+n+1,cmp);
 	for (int i=1;i<=n;i++) sign[sg[i]]=i;
//la是从哪里过来，Trs只能从上面过来，ma是当前距离，Ans是答案距离
 	for (int i=1;i<=n;)
 	 {
 	 	int ri=i;
 	 	while (ri<n&&wz[sg[ri+1]][1]==wz[sg[ri]][1]) ri++;
 	 	for (int j=i;j<=ri;j++)
 	 	 for (int k=0;k<3;k++)
 	 	  {
 	 	  	 int l=Ans[dir[sg[j]][k]];
 	 	  	 if (l>ma[sg[j]])
 	 	  	   ma[sg[j]]=Ans[sg[j]]=l,Trs[sg[j]]=k;
 	 	  }
 	 	int Ma=0;
 	 	for (int j=i;j<=ri;j++)
 	 	 {
 	 	 	if (Ma&&ri-Ma+ma[sg[Ma]]>Ans[sg[j]])
 	 	 	  Ans[sg[j]]=ri-Ma+ma[sg[Ma]],la[sg[j]]=sg[Ma];
 	 	 	if (!Ma||ri-j+ma[sg[j]]>ri-Ma+ma[sg[Ma]]) Ma=j;
 	 	 }
 	 	Ma=0;
 	 	for (int j=ri;j>=i;j--)
 	 	 {
 	 	 	if (Ma&&Ma-i+ma[sg[Ma]]>Ans[sg[j]])
 	 	 	  Ans[sg[j]]=Ma-i+ma[sg[Ma]],la[sg[j]]=sg[Ma];
 	 	 	if (!Ma||j-i+ma[sg[j]]>Ma-i+ma[sg[Ma]]) Ma=j;
 	 	 }
 	 	for (;i<=ri;i++) Ans[sg[i]]++;
 	 }
 	cout <<Ans[n]-1<<endl;Up(n);puts("");
 	return;
 }
bool BFS()
 {
 	memset(h,0,sizeof(h));
 	for (int i=1;i<=n;i++) cur[i]=fi[i];
 	for (int i=_T;i<N;i++) cur[i]=fi[i];
 	int le=1,ri=1;h[_S]=1;li.push(_S);
    while (!li.empty())
     {
     	int k=li.front();li.pop();
     	for (int i=fi[k];i;i=c[i][1])
     	 if (c[i][2]&&!h[c[i][0]])
     	   h[c[i][0]]=h[k]+1,li.push(c[i][0]);
     }
    return h[_T]>0;
 }
int DFS(int x,int y)
 {
 	int k,l=0;
 	if (x==_T) return y;
 	for (int i=cur[x];i&&y;i=c[i][1])
 	 if (c[i][2]&&h[c[i][0]]==h[x]+1)
 	  {
 	  	 k=DFS(c[i][0],min(y,c[i][2]));cur[x]=i;
 	  	 if (k) l+=k,y-=k,c[i][2]-=k,c[i^1][2]+=k;
 	  }
 	return l;
 }
inline void line(int x,int y)
 {Line(x,y,INF);Line(_S,y,1);Line(x,_T,1);flag[y]=true;}
void Trans(int x)
 {
 	if (vis[x]) return;vis[x]=true;
 	for (int i=0;i<3;i++)
 	 if (ma[x]==Ans[dir[x][i]]&&dir[x][i]) line(x,dir[x][i]);
 }
void Clear()
 {while (!li.empty()) li.pop();}
void Build()
 {
 	flag[n]=true;
 	for (int i=n;i;)
 	 {
 	 	int le=i,Ma=0;
 	 	while (le>1&&wz[sg[le-1]][1]==wz[sg[i]][1]) le--;
 	 	for (int j=le;j<=i;j++)
 	 	 {
 	 	 	if (flag[sg[j]])
 	 	 	 {
 	 	 	 	if (!la[sg[j]]) Trans(sg[j]);
 	 	 	 	if (Ma==Ans[sg[j]])
 	 	 	 	 while (!li.empty())
 	 	 	  	   Trans(li.front()),li.pop();
 	 	 	 }
 	 	 	if (ma[sg[j]]+i-j+1>Ma)
 	 	 	  Clear(),li.push(sg[j]),Ma=ma[sg[j]]+i-j+1; else
 	 	 	if (ma[sg[j]]+i-j+1==Ma)
 	 	 	  li.push(sg[j]);
 	 	 }
 	 	Ma=0;Clear();
 	 	for (int j=i;j>=le;j--)
 	 	 {
 	 	 	if (flag[sg[j]]&&Ma==Ans[sg[j]])
 	 	 	 while (!li.empty())
 	 	 	   Trans(li.front()),li.pop();
 	 	 	if (ma[sg[j]]+j-le+1>Ma)
 	 	 	  Clear(),li.push(sg[j]),Ma=ma[sg[j]]+j-le+1; else
 	 	 	if (ma[sg[j]]+j-le+1==Ma)
 	 	 	  li.push(sg[j]);
 	 	 }
 	 	i=le-1;
 	 }
 	return;
 }
void Flow()
 {
 	for (int i=1;i<=n;i++)
 	  Line(S,i,INF),Line(i,T,INF);
 	Build();
 	while (BFS()) DFS(_S,INF);
 	Line(T,S,INF);
 	while (BFS()) DFS(_S,INF);
 	cout <<c[ss][2]<<endl;
 	return;
 }
int main()
 {
 	n=Read()+1;
 	for (int i=1;i<n;i++)
 	  wz[sg[i]=i][0]=Read(),wz[i][1]=Read();sg[n]=n;
 	DP();Flow();
    return 0;
 }