Crayfish

Memory limit: 32 MB

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:

1. Between houses the crayfish may only move using particular routes.
2. Each route is one-way, and connects two distinct houses. There could be more than one route connecting the same houses.
3. 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 .
4. 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.
5. 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).

Task

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.

Input

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 .

Output

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 .

Example

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.