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

Numbering path

Given the intersections connected by one-way streets in a city, you are to write a program that determines the number of different routes between each intersection. A route is a sequence of one-way streets connecting two intersections.

Intersections are identified by non-negative integers. A one-way street is specified by a pair of intersections. For example, j k indicates that there is a one-way street from intersection j to intersection k. Note that two-way streets can be modeled by specifying two one-way streets: j k and k j.

Consider a city of four intersections connected by the following one-way streets:

0 1

0 2

1 2

2 3

There is one route from intersection 0 to 1, two routes from 0 to 2 (the routes are 012 and 02), two routes from 0 to 3, one route from 1 to 2, one route from 1 to 3, one route from 2 to 3, and no other routes.

It is possible for an infinite number of different routes to exist. For example if the intersections above are augmented by the street 3 2, there is still only one route from 0 to 1, but there are infinitely many different routes from 0 to 2. This is because the street from 2 to 3 and back to 2 can be repeated yielding a different sequence of streets and hence a different route. Thus the route 023232 is a different route than 0232.

Input

Contains a sequence of city specifications. Each specification begins with the number of one-way streets in the city. The first number describes the amount of one-way streets in the city. It is followed by one-way streets given as pairs of intersections. Each pair j k represents a one-way street from intersection j to intersection k. In all cities, intersections are numbered sequentially from 0 to the "largest" intersection. All integers in the input are separated by whitespace.

There will never be a one-way street from an intersection to itself. No city will have more than 30 intersections.

Output

A square matrix of the number of different routes from intersection j to intersection k is printed. If the matrix is denoted M, then M[j][k] is the number of different routes from intersection j to intersection k. The matrix M should be printed in row-major order, one row per line.

If there are an infinite number of different paths between two intersections -1 should be printed. DO NOT worry about justifying and aligning the output of each matrix. All entries in a row should be separated by whitespace.

Time limit 1 second
Memory limit 128 MiB
Input example #1
7 0 1 0 2 0 4 2 4 2 3 3 1 4 3
Output example #1
0 4 1 3 2
0 0 0 0 0
0 2 0 2 1
0 1 0 0 0
0 1 0 1 0
Input example #2
9
0 1 0 2 0 3
0 4 1 4 2 1
2 0
3 0
3 1
Output example #2
-1 -1 -1 -1 -1
0 0 0 0 1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
0 0 0 0 0
Source Summer School 2010, Sebastopol, Day M.Medvedev