Q国有一些城市，城市间有一些单向道路，阿Q想知道以每座城市为起点可以到哪些城市，你能帮帮他吗？

输入格式

第一行输入 $n(1 \leq n \leq 100)，m(0 \leq m \le 1000)$，分别表示阿Q的王国的城市数和道路数。

接下来 m 行，每行两个不同的正整数 $u, v(1 \leq u, v \leq n)$，表示有一条从城市 u 到城市 v 的道路。

输出格式

输出 n 行，每行 n 个数，用空格隔开，每个数是 0 或者 1 ，其中第 i 行第 j 列的数表示以城市 i 为起点能否到达城市 j ，其中 0 表示不可到达，1 表示可以到达。

样例输入

3 2
1 2
1 3

样例输出

1 1 1
0 1 0
0 0 1