Problem L
TraveLog
After a long time apart, Alice and Bob have reunited. They
live in a country with
When Alice asked Bob which path he took, he was stunned to
find he didn’t remember. Bob is efficient, and drove without
stopping, and knows there is no path faster than the one he
took. He also has a brand new National Adventuring Company
(NAC) TraveLog! Every time Bob drives through a city, the
TraveLog records the time between when he left city
![\includegraphics[width=0.8\textwidth ]{input1.png}](/problems/travelog/file/statement/en/img-0001.png)
In the above layout, there are two possible fastest paths
Bob can take from city
Unfortunately, the memory in Bob’s TraveLog is corrupted. Bob thinks that some of the times are gone, and the remaining times are shuffled arbitrarily. Given what remains of the TraveLog, can you reconstruct Bob’s path?
Input
The first line of input contains three integers
Each of the next
Each of the next
Output
The output format depends on the number of paths consistent with Bob’s TraveLog.
-
If there is no path consistent with Bob’s TraveLog, output
. -
If multiple paths are consistent with Bob’s TraveLog, output
. -
Otherwise, on the first line, output the number of cities on Bob’s path. On subsequent lines, output the cities Bob visited, one per line, in the order he visited them.
Sample Input 1 | Sample Output 1 |
---|---|
5 5 2 1 2 3 2 3 4 3 5 2 1 4 5 4 5 4 5 9 |
3 1 4 5 |
Sample Input 2 | Sample Output 2 |
---|---|
6 8 2 1 2 1 2 3 2 3 6 8 1 4 3 4 5 4 5 6 4 5 2 7 1 6 13 0 3 |
1 |
Sample Input 3 | Sample Output 3 |
---|---|
2 1 1 1 2 10 5 |
0 |