*Not an official ACM page*

[Problem F
| 1994 East-Central Regional problem set
| My ACM problem archive
| my home page]

### 1994 East-Central Regionals of the ACM International Collegiate Programming Contest

#### Problem E

## Cat and Mouse

In a house with many rooms live a cat and a mouse. The cat and the
mouse each have chosen one room as their "home". From their
"home" they regularly walk through the house. A cat can go
from room A to room B if and only if there is a cat door from room A
to room B. Cat doors can only be used in one direction. Similarly a
mouse can go from room A to room B if and only if there is a mouse
door from room A to room B . Also mouse doors can be used in only one
direction. Furthermore, cat doors cannot be used by a mouse, and mouse
doors cannot be used by a cat.
Given a map of the house you are asked to write a program that finds
out

- if there exist walks for the cat and mouse where they meet
each other in some room, and
- if the mouse can make a walk through at least two rooms, end in
its "home" room again, and along the way cannot ever meet
the cat. (Here, the mouse may not ever meet the cat, whatever the cat
does.)

For example, in the map, the cat can meet the mouse in rooms 0, 1, and
2. Also, the mouse can make a walk through two rooms without ever
meeting the cat, viz., a round trip from room 4 to 3 and back.
### Input

The input consists of integers and defines the configuration of the
house. The first line has three integers separated by blanks: the
first integer defines the number of rooms, the second the initial room
of the cat (the cat's "home"), and the third integer defines
the initial room of the mouse (the mouse's "home"). Next
there are zero or more lines, each with two positive integers
separated by a blank. These lines are followed by a line with two _1's
separated by a blank. The pairs of positive integers define the cat
doors. The pair A B represents the presence of a cat door from room A
to room B. Finally there are zero or more lines, each with two
positive integers separated by a blank. These pairs of integers define
the mouse doors. Here, the pair A B represents the presence of a mouse
door from room A to room B.
The number of rooms is at least one and at most 100. All rooms are
numbered consecutively starting at 0. You may assume that all positive
integers in the input are legal room numbers.

### Output

The output consists of two characters separated by a blank and ended
by a new-line character. The first character is Y if there exist walks
for the cat and mouse where they meet each other in some
room. Otherwise, it is N. The second character is Y if the mouse can
make a walk through at least two rooms, end in its "home"
room again, and along the way cannot ever meet the cat. Otherwise, it
is N.
### Sample Input

(From example above)
5 2 4
0 1
1 0
2 0
3 2
4 1
-1 -1
0 2
1 4
2 3
3 0
3 1
3 4
4 3

### Sample Output

Y Y

This page maintained by
Ed Karrels.

Last updated September 20, 1999