In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].

If you are familiar with IRC chat, the support team is also reachable on PIRC network (`irc.pirc.pl`

) in `#szkopul`

channel. If you are not, just use email.

Please do not ask us things like "how to solve task XYZ?".

Please remember that the support team has to sleep sometimes or go to work in real life.

In Byteland there is a pond occupied by turtles. In this pond there are also houses, numbered from to . 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:

- Between houses the crayfish may only move using particular
*routes*. - Each route is one-way, and connects two distinct houses. There could be more than one route connecting the same houses.
- Crayfish can move
*normally*or*backwards*. Being in house and moving normally, the crayfish can move to house , if there exist a route from house to house . If the crayfish is moving backwards, then he can go from house to if there exist a route from to . - Some of the routes are
*special*. Just after using such route the crayfish changes his moving style - if he was moving normally, then he starts moving backwards and if he was moving backwards he starts moving normally. The crayfish cannot change its moving style anywhere else. - At the beginning of his migrations, the crayfish migrant moves backwards.
When visiting a friend, the crayfish does not change moving style.
At the end of his migration, the crayfish must move backwards
(if the last route was special, just before entering this
route the crayfish should move
*normally*).

Write a program which:

- reads the description of routes in a Byteland pond,
- for each house computes the number of friends the crayfish could visit, if he stayed at that house,
- writes the answer to the standard output.

The first line of the standard input contains two integers and (, ). These numbers denote respectively: the number of houses and the number of routes. In the following lines there are descriptions of particular routes, each on a separate line. Each description consists of three integers , and (, ). Integer denotes the starting house number, denotes ending house number. Route is special if and only if .

Exactly lines are to be written to the standard output. In the -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 .

For the input data:

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

the correct result is:

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.

*Task author: Szymon Acedanski.*