TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

100.0% (28/28)

Submission's AC Ratio

50.0% (49/98)

Tags

Description

在拜特蘭(Byteland)有一個池塘被烏龜們佔領。這間池塘也有許多房子,編號從1~N,每間房子都住著恰好一隻烏龜。

有一隻小龍蝦要從拜特美利加(Bytemerica)移民到拜特蘭。這隻小龍蝦非常喜歡裝熟而且所有烏龜都是他的朋友。

在他的拜訪中,他決定住在其中一隻烏龜的家裡,但問題來了,他要待在誰家?

小龍蝦希望搬到一個使他能拜訪越多朋友越好的家裡。

要拜訪朋友不是一件難事,但依然有許多潛規則:首先,要拜訪一隻烏龜必須要去到他家。第二,小龍蝦必須要回得了家。

我們假定小龍蝦將不能拜訪他所居住的家中的烏龜。

小龍蝦的移動被以下幾個規則限定著:

1. 小龍蝦要在房子間移動必須走特定的道路。

2. 每條道路都是單行道,連接著兩間相異的房子。同一間房子可能有不只一條道路。

3. 小龍蝦有兩種移動模式:正常跟倒退。假設他現在在房子A。如果他很正常而且存在一條A往B的道路,那麼他可以走到B。
如果他在倒退,那麼他要走到B必須存在一條B往A的道路。

4. 有些道路是特別的。走過這些道路會強迫小龍蝦改變他的移動模式。也就是如果他現在很正常,走過這條道路後會開始倒退;
反之如果他在倒退,走過這條道路會回覆正常。除此之外,小龍蝦沒有任何改變移動模式的方法。

5. 當小龍蝦要從他的居所出發時,他是倒退走路。用哪種方式拜訪其他烏龜都可以,但是回到家時一定也得是倒退。
(如果他是走特別道路回家,那麼就表示他踏上這條道路之前得是正常走路)。

請你寫一個程式對每間房子計算出住在那裡的話小龍蝦可以拜訪到幾隻烏龜。

Input Format

一個測試檔僅含單筆測資。

每筆測資第一行包含兩個數字1 ≤ N ≤ 10,000 以及1 ≤ M ≤ 100,000。

接下來有M行每行有三個數字a, b, s

其中a和b皆是1~N之內的正整數、s是0或1

表示有一條a→b的道路,s是1若且唯若這條道路是特殊的。

Output Format

輸出包含N行,每行包含一個整數。

第i行的數字表示住在編號i的房子可以拜訪到幾隻烏龜。

Sample Input 1

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

Sample Output 1

3
3
3
3
0

Hints

範例測資的圖片:

Problem Source

原TIOJ1686 / Algorithmic Engagements (PA) 2006 Round 4

Subtasks

No. Testdata Range Score
1 0 9
2 1 9
3 2 9
4 3 9
5 4 9
6 5 9
7 6 9
8 7 9
9 8 9
10 9 9
11 10 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1500 65536 262144 1
1 1500 65536 262144 2
2 1500 65536 262144 3
3 1500 65536 262144 4
4 1500 65536 262144 5
5 1500 65536 262144 6
6 1500 65536 262144 7
7 1500 65536 262144 8
8 1500 65536 262144 9
9 1500 65536 262144 10
10 1500 65536 262144 11