# 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 **0** → **1** → **2** and **0** → **2**), 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 **0** → **2** → **3** → **2** → **3** → **2** is a different route than **0** → **2** → **3** → **2**.

#### 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.

7 0 1 0 2 0 4 2 4 2 3 3 1 4 3

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

9 0 1 0 2 0 3 0 4 1 4 2 1 2 0 3 0 3 1

-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