e-olymp
Problems

The incidence matrix

The incidence matrix

Vertex of the graphuisincident toedgee, if uis oneof the endpoints ofedgee.

Similarly,an edgeeisincidentvertexu, ifone end of thee - is the pinnacle ofu.

The incidence matrixof a graphG=(V, E)isa rectangular tableof |V| rows and |E| columns, whereat the intersection ofthe i-throw andj-th columnwrittenone ifvertexiis incident toedgej, and zerootherwise.

Givenan undirected graph.Bringitthe incidence matrix.

Input

The first line ofthe input fileare given numbersN and M areseparated by a space- the number ofvertices andedges in the graph, respectively (1N1000, 0M10000). The nextMlines containtwo numbersui and viinspace (1ui, viN); each suchline means thatthere is an edgein the graphbetween the verticesui and vi. The ribsare numbered in theorder in whichthey are givenin the input file,starting with one.

Output

Derivethe output fileN linesofMnumbers each.j-th element of thei-th rowmust be equal tounity ifvertex iis incident toedgej andzero otherwise.Separateadjacentrow elementswith a single space.

Time limit 1 second
Memory limit 64 MiB
Input example #1
3 2
1 2
2 3
Output example #1
1 0
1 1
0 1