Edgetown's Traffic Jams |
Given two intersections X and Y in Edgetown, the distance from X to Y is measured as the minimum number of
blocks that should be traveled going from X to Y. The following diagram shows a possible configuration with eight blocks and
eleven intersections (marked with asterisks).
Lately there have been traffic jams at several points, almost at all times. Experts recommend a simple solution: just change some two-way blocks to be one-way blocks. However, it is clear that this should be done carefully, because accessibility among city points may be lost. On the other hand, even if accessibility is guaranteed, it is possible that distances between specific intersections may be significantly augmented.
After a lot of discussions, the Mayor's advisers have recommended to accept any proposal that increases the distance
between any two intersections by a factor A augmented by a constant B, with respect to the old configuration (i.e., if the
actual distance from one intersection to another is x, then the new distance should be at most
A . x + B).
You are hired to develop a program to decide if a given proposal to orient city blocks satisfies the requirements.
There are several cases to analyze. Each case is described with a set of lines:
The last test case is followed by a line containing a single `0'.
For each case print one line with the word `Yes' if the proposal satisfies the given requirements, or the word `No' otherwise. Answers should be left aligned.
5 1 2 3 2 1 5 3 4 5 1 4 3 5 5 2 3 4 1 2 2 5 3 1 4 4 5 5 3 1 2 5 1 2 3 2 1 5 3 4 5 1 4 3 5 5 2 3 4 1 2 2 5 3 1 4 4 5 5 3 2 0 3 1 2 2 1 3 3 1 2 1 2 2 3 3 1 0 2 0
Yes No Yes