Polish version    English version  
  History of OI


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN

Task: Dicing


Dicing is a two-player game and its outcome is fully random. Lately its popularity increases all over Byteotia. There is even a special club for dicing amateurs in the capital city of Byteotia. The club patrons take their time talking to each other and playing their favourite game with a randomly chosen opponent every once in a while. Everyone who wins the most games one day gains the title of the lucky chap. Sometimes it happens that the night at the club is a quiet one and only few games are played. It is a time when even one win can make you a lucky chap.

Once upon a time a most unlucky fellow, Byteasar, won the glorious title. He was so deeply shocked that he completely forgot how many games he had won. Now he is wondering how good his luck was and whether fortune finally smiled upon him - perhaps his luck changed for good? He knows exactly how many games and between whom were played that lucky night. However, he does not know the results. Byteasar desires to find out what is the smallest number of wins that could provide the title of the lucky chap. Be a good fellow and help him satisfy his curiosity!

Task

Write a programme that:
  • for each game played reads from the standard input the pair of players who competed in it.
  • finds the smallest number k, such that a set of games' outcomes exists in which each player wins k games at the most,
  • writes the number k and the results of games in the found set to the standard output.

Input

In the first line of the standard input there is a pair of integers n and m separated by a single space, 1 <= n <= 10 000, 0 <= m <= 10 000; n denotes the number of players, while m is the number of games. The players are numbered from 1 to n. In the following m lines there are pairs of players' numbers depicting the sequence of games, separated by single spaces. One pair may occur many times in the sequence.

Output

The first line of the standard output should contain the determined number k. For each pair of players' numbers a, b specified in the ith line of the input, in the ith line of the output the number 1 should be written if the player no. a wins against player no. b in the found set of outcomes, or 0 otherwise.

Example

For the following input data:
4 4
1 2
1 3
1 4
1 2
The correct answer is:
1
0
0
0
1



Print friendly version