Problem : 330 - Crayfish

Problem Statistics

Solved Member: 15　　Submission: 59　　User Tried: 16

Statement:

有一隻很可愛的魚，簡稱可魚(Crayfish)，這隻魚會在一張有向圖上游來游去。

每條邊用三個數字表示，a, b, s 表示有一條a->b的邊，若s=1表示此邊為特別邊。

一開始可魚是倒著游，也就是他能從A游到B若且唯若有一條邊B->A。

但是當他走過特別的邊時他會發生變化：

如果他原本是倒著游會變成正著游、正著游會變倒著游。

但是不管他怎麼亂游，他一定要以倒著游的狀態回到起點。

試問對於每個點v，從v點出發並要回到v點最多能經過多少其他的點(不含起點，可以重複走點/邊)。
回到 v 點時，必須要是倒著走的狀態才行。（跟出發時的狀態一樣）

Input:Output:

第一行有兩個正整數V,E(1 <= V <= 10000, 1 <= E <= 100000)，表示點與邊的數目。

接下來有E行，每行三個整數a b s(1 <= a,b <= V, s ∈ {0,1})，表示a到b有一條有向邊，若s=1表示此邊是特別邊，若s=0表示此邊是正常邊。

請輸出V行，每行一個數字依序表示，他從第i個點出發能經過最多多少個點，並回到出發點。

Sample Input:Sample Output:

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

3
3
3
3
0

HINT:

Source:

PA 2006 Round 4

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1	1000ms	65536kb	10
2	1000ms	65536kb	10
3	1000ms	65536kb	10
4	1000ms	65536kb	10
5	1000ms	65536kb	10
6	1000ms	65536kb	10
7	1000ms	65536kb	10
8	1000ms	65536kb	10
9	1000ms	65536kb	10
10	1000ms	65536kb	10