Transitive closure

Input

The directed graph is given with the list of edges. The first line contains the number of vertices n~(1 \le n \le 100). Each of the next lines contains two vertices $a$ and b~(1 \le a, b \le n) describing the directed edge from $a$ to $b$.

Output

Print the adjacency matrix of the transitive closure of the directed graph.

Examples