Transitive closure

Find the transitive closure of the directed graph.

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