图论神题……不过贪心的思路很简单，每次选择一个未染色的点，满足它在未染色的点中已染色邻接点个数最多，用一个可用的最小的颜色对它染色后加入已染色集合。
证明详见WC2009讲稿 弦图与区间图-CDQ
这题最快可以用桶优化到$O(n+m)$，不过n只有10000，直接暴力$O(n^2 + m)$可过