Problem 4: no Exit: the Streets of Womanshoetan
Background:
Main street starts at West End Gate and ends at East Side Arch.
All the streets in Woosenten (our town name is affectionately so
pronounced by the locals) are one way. Many neighborhoods exist
which have only one entrance. This means the residents have to
go against at least one street direction to get out of the neighborhood.
They like it this way, and the police know only to ticket non-locals
for driving the wrong way on these one way streets. But the complaints
are mounting up and it has been decided to post "No Outlet" signs
at the beginning of each block of a street which, if you take it,
leads into one of these un-legally-exitable neighborhoods.
Only those no-exit blocks which are reachable from West End Gate or
East Side Arch need the sign.
To put it in other words, put a sign on a block if and only if the
starting intersection of the block is reachable from an end of Main Street,
but neither end of Main Street can be reached from the ending intersection
of the block .
Input:
The input will consist one or more street plans.
The intersections are numbered with non-negative integers.
West End Gate has number 0 and East Side Arch has 1.
A street plan consists of a descriptive line followed by a sequence of
intersection pairs (i, j) denoting blocks. Each block is one way from the
first intersection number
to the second. The street plan is terminated by a pair containing at
least one negative number. Intersection numbers will have at most three digits.
Output:
For each street plan, output the identifying line followed by the
list of blocks (i,j) that require
"No Outlet" signs, one per line. Terminate the output for a given street plan
with a blank line. You may list the blocks in any order.
Sample Input:
Trivialton
(0, 1)
(1, 2)
(2, 3)
(-1, 0)
Upper Womanshoetan streets
(0, 2)
(2, 1)
(1, 0)
(0, -3)
Lower Womanshoetan streets
(0, 2)
(0, 3)
(0, 4)
(0, 5)
(2, 222)
(3, 33)
(4, 44)
(5, 55)
(222, 33)
(33, 1)
(2, 1)
(1, 2)
(2, 0)
(44, 55)
(66, 55)
(-1, -1)
Sample Output:
Trivialton
(1, 2)
(2, 3)
Upper Womanshoetan streets
Lower Womanshoetan streets
(0, 4)
(0, 5)
(4, 44)
(5, 55)
(44, 55)