# The incidence matrix

# The incidence matrix

Vertex of the graph**u**is*incident* toedge**e**, if **u**is oneof the endpoints ofedge**e**.

Similarly,an edge**e**is*incident*vertex**u**, ifone end of the**e** - is the pinnacle of**u**.

*The incidence matrix*of a graph**G=(V, E)**isa rectangular tableof |**V**| rows and |**E**| columns, whereat the intersection ofthe **i**-throw and**j**-th columnwrittenone ifvertex**i**is incident toedge**j**, and zerootherwise.

Givenan undirected graph.Bringitthe incidence matrix.

**Input**

The first line ofthe input fileare given numbers**N** and **M** areseparated by a space- the number ofvertices andedges in the graph, respectively (**1** ≤ **N** ≤ **1000**, **0** ≤ **M** ≤ **10000**). The next**M**lines containtwo numbers**u _{i}** and

**v**inspace (

_{i}**1**≤

**u**,

_{i}**v**≤

_{i}**N**); each suchline means thatthere is an edgein the graphbetween the vertices

**u**and

_{i}**v**. The ribsare numbered in theorder in whichthey are givenin the input file,starting with one.

_{i}**Output**

Derivethe output file**N** linesof**M**numbers each.**j**-th element of the**i**-th rowmust be equal tounity ifvertex **i**is incident toedge**j** andzero otherwise.Separateadjacentrow elementswith a single space.

3 2 1 2 2 3

1 0 1 1 0 1