1929 . 偏序關係
TopCoder
Tags
Description
還記得大陸人的話嗎？
「操作分治主要用途是结合其它几种方法来解决高维偏序问题（竞赛中常见的主要是三维偏序问题）」
那麼什麼是偏序呢？
我們說一個定義在一個集合$X$上的關係$\leq$是一個「偏序關係」，如果以下三條式子滿足：
一、自反性：$\forall x\in X,x\leq x$
二、反對稱性：$\forall x,y\in X, [x\leq y\wedge y\leq x]\Rightarrow x=y$
三、傳遞性：$\forall x,y,z\in X,[x\leq y\wedge y\leq z]\Rightarrow x\leq z$
簡單來說，任何一個元素都小於等於自己本身。如果兩個元素互相小於等於，那麼他們就是同一個元素。如果甲小於等於乙，乙又小於等於丙，那麼甲也小於等於丙。
既然理解什麼是偏序了，那就馬上來一題試試身手吧！
$X$中有一些元素$x_1, x_2, \dots, x_n$（不一定相異）使得$X=\{x_i|1\leq i\leq n\}$。令$\leq$是定義在$X$上的偏序關係。已知$(X,\leq)$是全序集（也就是，對於所有$X$中的任兩個元素$x,y$，$x\leq y$和$y\leq x$至少有一者成立）。給定一些$x_1,x_2,\dots,x_n$之間的偏序關係，請計算$|X|$的最大值，並給出其中一個達到最大值的偏序關係。
Input Format
第一行包含兩個正整數$n\leq 10^ 6, m\leq 10^ 6$，代表（不一定相異的）元素個數以及給定的偏序關係個數。
之後的$m$行，每行會有兩個正整數$1\leq i,j\leq n$，代表$x_i\leq x_j$。保證不會有重複的偏序關係。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0~4) | $n\leq 800$ | 21 |
| 2 (5~9) | $n,m\leq 10^ 4$ | 36 |
| 3(0~14) | 無 | 43 |
Output Format
請輸出兩行。第一行含有一個正整數$k$，代表$|X|$的最大值。第二行含有$n$個1到$k$的正整數，代表其中一個達到最大值的偏序關係。這裡第$i$個數是$r_i$的意思是$x_i$在$X$中是第$r_i$小的。若仍不理解，請見範例輸出輸入。
Sample Input 1
1 2
2 3
3 4
3 2
1 4
Sample Output 1
1 2 2 3
Hints
範例測資中，$x_2\leq x_3$且$x_3\leq x_2$，故$x_2=x_3$，也就是說相異元素個數至多3個。而令$x_1$是第一小，$x_2,x_3$是第二小，$x_4$是第三小（也就是說$x_1\leq x_2= x_3\leq x_4$）時符合所有給定的偏序關係。
Problem Source
Problem set / Description by Paupière
建國中學105學年度校內第六次模擬賽pB
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~4 | 21 |
| 2 | 5~9 | 36 |
| 3 | 0~14 | 43 |