| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 12802 | Least Skill Point |
|
Description
In RPG games, how to spend minimal skill points to learn the needed skill is always a challenge for gamers. (The needed skill point is the same.)
Input
First-line contains two integers N, M. Where N is the number of skills and M is the number of relations.
The following two lines are two characters for the starting skill you already learned and the target skill you want to learn.
Following M lines contain one edge each, in form A B. This means that there exists a path from skill A to skill B. (all the needed skill points are 1)
Output
In the first line, please print the minimal cost you need to spend to learn the skill.
In the second-line please print the node on the shortest path. There is no white space or newline in the end.