Hide

Problem F
Distracted

/problems/distracted/file/statement/en/img-0001.jpg
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?

Input

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.

Output

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 ?.

Scoring

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

Please log in to submit a solution to this problem

Log in