Distracted

Charles Chaplin in *Pay Day* (1922).

Everybody is either married or unmarried. Can you determine if a married person is looking at an unmarried person?

The first line of input consists of two integers: the total
number $N$ of people, and
the number $L$ of these
people who are looking at somebody else. You can assume
$0< N$ and $0\leq L\leq N$. Then follow
$N$ lines, one for every
person, giving the person’s name followed by their marital
status. People have unique names consisting of $1$ to $10$ letters from the English
alphabet. Their marital status is given as “m” if you know that
they are married, “u” if you know that they are unmarried, and
“?” if their marital status is unknown to you — even though
these people are either married or unmarried, you don’t know
which. Then follow $L$
lines of the form “`Alice ->
Charlie`”, meaning that Alice is looking at Charlie. You
have complete information about who is looking at whom, nobody
is looking at themselves, and nobody is looking at more than
one other person.

Print `1` if some married person is
looking at an unmarried person. Print `0` if no married person is looking at an
unmarried person. If this cannot be determined, print
`?`.

Group |
Points |
Limits |

1 |
23 |
$N\leq 3$, everybody’s marital status is known |

2 |
24 |
$N \leq 3$ |

3 |
25 |
$N \leq 12$ |

4 |
28 |
$N \leq 50\, 000$ |

Sample Input 1 | Sample Output 1 |
---|---|

3 2 Alice m Bobbie u Charlie m Alice -> Charlie Charlie -> Bobbie |
1 |

Sample Input 2 | Sample Output 2 |
---|---|

3 2 Alice m Bobbie ? Charlie m Alice -> Charlie Charlie -> Bobbie |
? |

Sample Input 3 | Sample Output 3 |
---|---|

3 2 Alice m Bobbie m Charlie m Alice -> Charlie Charlie -> Bobbie |
0 |