e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Floyd - Warshall + Transitive closure

Transitive closure

Find the transitive closure of the directed graph.

Input

Directed graph is given with the list of edges. First line contains number of vertices n (1n100). Each of the next lines contains two vertices a and b (1a, bn) describing the directed edge from a to b.

Output

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

prb10157.gif

Time limit 1 second
Memory limit 128 MiB
Input example #1
4
4 1
1 2
3 4
Output example #1
0 1 0 0 
0 0 0 0 
1 1 0 1 
1 1 0 0 
Author Mykhailo Medvediev