TopCoder

餘切
pooh is 8

User's AC Ratio

91.3% (42/46)

Submission's AC Ratio

50.9% (82/161)

Tags

Description

還記得大陸人嗎?
「操作分治主要用途是结合其它几种方法来解决高维偏序问题(竞赛中常见的主要是三维偏序问题)」
那麼什麼是偏序呢?

我們說一個定義在一個集合X上的關係是一個「偏序關係」,如果以下三條式子滿足:
一、自反性:xX,xx
二、反對稱性:x,yX,[xyyx]x=y
三、傳遞性:x,y,zX,[xyyz]xz
簡單來說,任何一個元素都小於等於自己本身。如果兩個元素互相小於等於,那麼他們就是同一個元素。如果甲小於等於乙,乙又小於等於丙,那麼甲也小於等於丙。

既然理解什麼是偏序了,那就馬上來一題試試身手吧!

X中有一些元素x1,x2,,xn(不一定相異)使得X={xi|1in}。令是定義在X上的偏序關係。已知(X,)是全序集(也就是,對於所有X中的任兩個元素x,yxyyx至少有一者成立)。給定一些x1,x2,,xn之間的偏序關係,請計算|X|的最大值,並給出其中一個達到最大值的偏序關係。

Input Format

第一行包含兩個正整數n106,m106,代表(不一定相異的)元素個數以及給定的偏序關係個數。
之後的m行,每行會有兩個正整數1i,jn,代表xixj。保證不會有重複的偏序關係。

子任務(測資) 額外限制 分數
1 (0~4) n800 21
2 (5~9) n,m104 36
3(0~14) 43

Output Format

請輸出兩行。第一行含有一個正整數k,代表|X|的最大值。第二行含有n個1到k的正整數,代表其中一個達到最大值的偏序關係。這裡第i個數是ri的意思是xiX中是第ri小的。若仍不理解,請見範例輸出輸入。

Sample Input 1

4 5
1 2
2 3
3 4
3 2
1 4

Sample Output 1

3
1 2 2 3

Hints

範例測資中,x2x3x3x2,故x2=x3,也就是說相異元素個數至多3個。而令x1是第一小,x2,x3是第二小,x4是第三小(也就是說x1x2=x3x4)時符合所有給定的偏序關係。

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 1048576 262144 1 3
1 1000 262144 262144 1 3
2 1000 262144 262144 1 3
3 1000 262144 262144 1 3
4 1000 262144 262144 1 3
5 1000 262144 262144 2 3
6 1000 262144 262144 2 3
7 1000 262144 262144 2 3
8 1000 262144 262144 2 3
9 1000 262144 262144 2 3
10 2000 262144 262144 3
11 2000 262144 262144 3
12 2000 262144 262144 3
13 2000 262144 262144 3
14 2000 262144 262144 3