TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

Description

傳說在遙遠的古代,整個地球的大陸是一整塊,整塊大陸上有 n 個城市。這些城市間有共有 m條道路相連接,不過有趣的是這些道路只能夠單向通行。有一天
上帝決定把整塊大陸切成幾塊形成各自的國家。分割的策略就是把原本就可以互
相聯絡的幾個城市當成一個國家(如果有一條路徑從城市i 到城市 j 且有一條路徑從城市j 到城市 i,則城市i 和城市 j 就在同一個國家) 。上帝想請你幫一個忙,他想知道每個國家的大小。也就是每個國家到底包含了幾個城市。


以下是一個簡單的例子:

如果有一條單行道從城市i 接到城市 j 用(i,j)表示

如果一開始有 3 個城市,然後有3 條單行道(1, 2), (2, 1), (2, 3)

則可以分成兩個國家,分別包含了2 個城市(1, 2)和 1個城市(3)。

Input Format

輸入檔中會有多筆資料,每一組資料的第一行第一行包含了城市數量n(1<=n<=100000)和單行道的數量 m(1<=m<=2100000),接下來 m行,每一行中都包含兩個數字 i, j 代表有一條單行道從城市 i 連到城市 j(注意兩個城市間可能有不只兩條的單行道)。

Output Format

對於每一組資料輸出一行,內容是排序過後每個國家的大小。

Sample Input 1

3 3 
1 2 
2 1 
2 3 
 
2 2 
1 2 
2 1

Sample Output 1

1 2
2 

Hints

Problem Source

Migrated from old NTUJ.

NPSC預賽

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 200