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

Hint


Source