시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 1 | 1 | 1 | 100.000% |
In Byteland there is a pond occupied by n turtles. In this pond there are also n houses, numbered from 1 to n. In each of these houses lives exactly one turtle. Soon the crayfish migrant (who lives in Bytemerica) will come to Byteland. This crayfish is very social and all turtles are his friends. During his visit, the crayfish plans to stay at one of his friend's house. But the problem is, in which house he should stay.
Crayfish migrant is interested in houses which will allow him to visit as many friends as possible. One could think, that visiting friends is not a problem, but in a Byteland pond it is harder that is seems. Firstly, in order to visit someone, one must reach his house. Secondly, one must also get back. We assume, that the crayfish migrant will not visit the turtle, in whose house he will stay.
Crayfish moves according to the following rules:
Write a program which:
The first line of the standard input contains two integers n and m (1 ≤ n ≤ 10 000, 1 ≤ m ≤ 100 000). These numbers denote respectively: the number of houses and the number of routes. In the following m lines there are descriptions of particular routes, each on a separate line. Each description consists of three integers a, b and s (1 ≤ a, b ≤ n, s ∈ {0, 1}). Integer a denotes the starting house number, b denotes ending house number. Route is special if and only if s = 1.
Exactly n lines are to be written to the standard output. In the i-th line exactly one integer is to be written, this integer is the number of friends the crayfish could visit, if he stayed at house number i.
5 5 2 1 1 2 3 0 3 4 0 4 2 0 5 3 1
3 3 3 3 0
Staying at house number 1 the crayfish can visit friends from houses 2, 3, 4. Staying at house number 2 the crayfish can visit friends from houses 3, 4, 5. Staying at house number 3 the crayfish can visit friends from houses 2, 4, 5. Staying at house number 4 the crayfish can visit friends from houses 2, 3, 5. Staying at house number 5 the crayfish can visit none of his friends.
Contest > Algorithmic Engagements > PA 2006 4-2번