2003 . 樹狀圖
TopCoder
Tags
Description
上了魔法大學正在修普生的小向，寫了一個畫出物種關係樹狀圖的程式。程式執行的結果大概就像下面這樣：
每一條橫線都代表他們所連接的豎線所連接到的物種們有關係。愈低的橫線代表關係愈近，而愈高的橫線則代表關係愈遠。
然而小向太久沒寫code了，所以寫出來的程式有兩個問題：第一個就是這個樹狀圖不一定是連通的，不過其實這沒有什麼關係；第二個問題是這個樹狀圖可能長得亂亂的，如下圖：
這種有相交的樹狀圖長得實在不是很討喜。不過小向發現只要適當地變換底下物種的順序，就可以幫亂亂的樹狀圖變成跟第一張圖一樣乾淨的樹狀圖。
小向想破了頭還是想不出要怎麼把這個bug給修好，所以他只好把這個題目放在TIOJ了。
Input Format
第一行有兩個整數$0<N\leq 10^ 6, 0\leq M < N$, 分別代表物種的個數以及橫線的個數。
接下來的$M$行中每一行都會有一條橫線以及他所連接的豎線的訊息。具體來說，每一行都會有整數$0\leq Y\leq 10^ 9, 2\leq L\leq N, 1\leq V_1, V_2, \ldots, V_L\leq N$, 分別代表橫線的y軸值，橫線所連接的豎線個數，以及每條豎線連接的物種團中的某一個物種。
保證所給的測資可以畫出合法的樹狀圖。也就是說對於每個物種，他所會連到的橫線的高度都相異，而且每一條橫線和物種團之間最多只會有一條豎線。但不保證給定的樹狀圖是連通的。
Output Format
輸出一行，包含$N$個用空格隔開的數，代表其中一種乾淨的樹狀圖的排法。若有很多種，請輸出字典序最小的答案。
Sample Input 1
10 3 2 4 5
40 2 1 5
20 2 1 3
30 2 3 6
Sample Output 1
Hints
本題的輸入輸出量非常大，建議C++輸入輸出使用者加入std::cin.tie(0);以及ios_base::sync_with_stdio(0)兩行，同時不要使用C式輸出。
Problem Source
Problem Set / Description by Paupière
題目取自MIT ACM ICPC校內團體賽第四題強化版
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~4 | $N\leq 10$ | 8 |
| 2 | 0~9 | $N\leq 10^ 4$ | 12 |
| 3 | 0~14 | $N\leq 10^ 5$ | 30 |
| 4 | 0~19 | 無額外限制 | 50 |