QAQ
【题目分析】
谁能告诉我为什么我的网络流炸了吗。。。。。。。。（我相信是SPJ的锅这年头暴力不好打啊）
所以我们按x排序，然后就是要找到序列中严格上升序列的最少个数，然后。。。。duang。。。。Dilworth定理（上升序列的最少个数等于最长不上升子序列长度）
关于方案，我们在求最长不上升子序列的时候，可以替换的位置一定是严格小于的关系，所以这两个一定能放在一个蛋糕中，最后每个蛋糕一定放在了1~最长不上升子序列长度的地方。
over。。。。。。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;int Read()
{int i=0,f=1;char c;for(c=getchar();(c>'9'||c<'0')&&c!='-';c=getchar());if(c=='-')f=-1,c=getchar();for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0';return i*f;
}struct Cake{int x,y,id;friend inline bool operator<(const Cake &a,const Cake &b){return a.x<b.x;}
}cake[MAXN];int n,last,belong[MAXN],f[MAXN];int main()
{n=Read();for(int i=1;i<=n;++i)cake[i].x=Read(),cake[i].y=Read(),cake[i].id=i;sort(cake+1,cake+n+1);for(int i=1;i<=n;++i){int l=1,r=last;while(l<=r){int mid=(l+r)>>1;if(f[mid]<cake[i].y)r=mid-1;elsel=mid+1;}f[l]=cake[i].y;if(l>last)last=l;belong[cake[i].id]=l;}printf("%d\n",last);for(int i=1;i<=n;++i)printf("%d ",belong[i]);return 0;
}
