Problem F
Distracted
Languages
da
en
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 |
