Problem F
Topic X
You are at the annual holiday gathering with extended family, sitting around a table having your traditional post-dinner conversation. You know that awkward topic X is going to come up, as it does every year, but you want to avoid it as long as possible. You have had these conversations so many times that you know how long each topic will take to discuss, and you also know to which other topics you can steer the conversation from a given topic. Given this information, you want to write a program to figure out how long you can avoid topic X.
Input
Input begins with an integer $t$, the number of topics (not including the topic to be avoided). The next line contains the name of the starting topic, followed by a space and the name of the topic which you want to avoid. $t$ lines follow, one per topic other than the topic to be avoided. Each of the $t$ lines contains a number of space-separated tokens as follows: first comes the name of a topic; then an integer $m$ giving the number of minutes that topic will be discussed; then an integer $n$, followed by a list of $n$ topics to which you can steer the conversation following the topic at the beginning of the line. These $n$ topics will all be distinct from each other and from the topic at the beginning of the line.
Names of topics consist of anywhere from $1$ up to $20$ letter, digit, or underscore characters. You may assume that $1 \leq t \leq 1000$, and for each $m$ and $n$ you may assume $1 \leq m \leq 100$ and $1 \leq n \leq 100$.
The starting topic will always be one of the $t$ listed topics, which will all be unique. There will always be at least one path from the starting topic to the topic you want to avoid.
Output
If it is possible to avoid topic X forever, output SAFE. Otherwise, output the maximum number of minutes for which topic X can be avoided.
Explanation of sample inputs and outputs
Sample 1
From the economy it is possible to steer the conversation either to politics or the weather. However, once you start talking about the weather it is inevitable that Bob’s surgery will come up, so it is better to steer the conversation to politics; after that you can steer the conversation to the weather, and then finally Uncle Bob’s surgery. The output is the total amount of time spent talking about things other than Bob’s surgery, which is $10 + 7 + 5 = 22$.
Sample 2
The only difference from sample input 1 is that after talking about the weather, it is now possible to steer the conversation back to the economy. You can therefore repeatedly discuss the economy, politics, and the weather forever, without ever discussing the dreaded topic of Uncle Bob’s surgery.
Sample 3
Although you could in theory discuss politics and the weather forever, it is not possible to steer the conversation there: the conversation starts on the economy, and from there it is inevitable that Bob’s surgery will be discussed next.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 the_economy uncle_bobs_surgery the_economy 10 2 politics weather politics 7 2 weather uncle_bobs_surgery weather 5 1 uncle_bobs_surgery |
22 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 the_economy uncle_bobs_surgery the_economy 10 2 politics weather politics 7 2 weather uncle_bobs_surgery weather 5 2 the_economy uncle_bobs_surgery |
SAFE |
| Sample Input 3 | Sample Output 3 |
|---|---|
3 the_economy uncle_bobs_surgery the_economy 10 1 uncle_bobs_surgery politics 7 1 weather weather 5 1 politics |
10 |
