e-olymp
Задачи

Матрица инцидентности

Матрица инцидентности

Вершина графа u называется инцидентной ребру e, если u является одним из концов ребра e.

Аналогично, ребро e называется инцидентым вершине u, если один из концов e - это вершина u.

Матрицей инцидентности графа G=(V, E) называется прямоугольная таблица из |V| строк и |E| столбцов, в которой на пересечении i-ой строки и j-го столбца записана единица, если вершина i инцидентна ребру j, и ноль в противном случае.

Дан неориентированный граф. Выведите его матрицу инцидентности.

Входные данные

В первой строке входного файла заданы числа N и M через пробел - количество вершин и рёбер в графе, соответственно (1N1000, 0M10000). Следующие M строк содержат по два числа ui и vi через пробел (1ui, viN); каждая такая строка означает, что в графе существует ребро между вершинами ui и vi. Рёбра нумеруются в том порядке, в котором они даны во входном файле, начиная с единицы.

Выходные данные

Выведите в выходной файл N строк, по M чисел в каждой. j-ый элемент i-ой строки должен быть равен единице, если вершина i инцидентна ребру j и нулю в противном случае. Разделяйте соседние элементы строки одним пробелом.

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные
Sample 1
3 2
1 2
2 3

Sample 2
2 2
1 1 
1 2

Выходные данные
Sample 1
1 0
1 1
0 1

Sample 2
1 1
0 1