Numbering Paths

Time Limit: 4000 ms Memory Limit: 32768 KiB

Problem Description

Background

Problems that process input  and generate a simple yes'' or  no''
answer  are  called  decision  problems.     One  class  of  decision
problems,  the NP-complete  problems,  are  not amenable  to  general
efficient  solutions.    Other problems  may  be simple  as  decision
problems, but  enumerating all possible yes''  answers may be  very
difficult (or at least time-consuming).

This problem  involves determining the number of routes  available
to an emergency vehicle operating in a city of one-way streets.

The Problem

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 kj.
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), 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

The input is a  sequence of city specifications.  Each  specification
begins  with the  number  of one-way  streets  in the  city  followed

by  that  many  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.   The input is  terminated
by end-of-file.
There  will never  be a  one-way street  from  an intersection  to

itself.  No city will have more than 30 intersections.

Output

For  each city  specification,  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.    Each  matrix
should  be preceded  by the  string  matrix for  city k''  (with  k
appropriately instantiated, beginning with 0).
If  there are an  infinite number of  different paths between  two

intersections a -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.

Sample Input

7 0 1 0 2 0 4 2 4 2 3 3 1 4 3
5
0 2
0 1 1 5 2 5 2 1
9
0 1 0 2 0 3
0 4 1 4 2 1
2 0
3 0
3 1

Sample Output

matrix for city 0
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
matrix for city 1
0  2  1  0  0  3
0  0  0  0  0  1
0  1  0  0  0  2
0  0  0  0  0  0
0  0  0  0  0  0
0  0  0  0  0  0
matrix for city 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