Trip to Acapulco
By Jadson José Monteiro Oliveira, Faculdade de Balsas 
Brazil
By Jadson José Monteiro Oliveira, Faculdade de Balsas Brazil
After having done a great trip to Acapulco some time ago, the villagers held a large meeting and decided to unite to travel again to this beautiful city. Although Mr. Madruga have had great luck and won the last trip with all expenses paid, the overall spending among all the villagers was gigantic and this time they are trying to save as much as possible, especially since no one from the village won paid trip again.
Turns out they were informed by a stranger, the best hotel in town (the same as they stayed last trip) will be with a promotion for a limited time, then how they want to save, they are looking to arrive in time to get the promotion.
Mr. Barriga responsible for managing the money spent is a man who understands numbers and now wants to use the power of technology to get some useful information before making the trip. As he already knows his skills as a mathematician and programmer, he hired you to develop a program that given all the information about the available cities and routes, the date and time they wish to leave the village and the date and time limit promotion hotel in Acapulco, indicate whether it is possible to reach Acapulco before the promotion ends, and which the least possible date and time, or if you cannot arrive in time to get the promotion.
The first input line contains a single integer QT (1 ≤ QT ≤ 100), indicating the number of test cases following. The first line of each test case is composed of two integers, N (2 ≤ N ≤ 105) and M (1 ≤ M ≤ 3x105) representing respectively the number of cities and the number of routes connecting those cities. The second line of each test case consists of the date and time that the villagers plan to go out and the third line of each case is made by the date and the time limit that the Acapulco hotel will be in promotion. The dates and times are described in the following notation: "DD/MM/YYYY - hh:mm:ss", where DD (1 ≤ DD ≤ 31) is the day of the month, MM (1 ≤ MM ≤ 12) represents the month of the year, AAAA (1970 ≤ AAAA ≤ 2100) is the year, hh (0 ≤ hh ≤ 23) represents the hours, mm (0 ≤ mm ≤ 59) represents minute, ss (0 ≤ ss ≤ 59) represents the seconds. The following M lines, each line containing two integers a and b and a date, indicating that there is a two-way route between the city a (0 ≤ a ≤ N-1) and b (0 ≤ b ≤ N-1) and the date in the format "DD -hh-mm-ss", representing the time required to go from a to b and vice-verse.
Consider that the village is the city of number 0 and city of Acapulco is the city of N-1 number.
For each test case, if it is possible to reach Acapulco before the promotion finalize, print two lines. In the first line the word "POSSIBLE" (without quotes) and the second line the smallest possible date in the following format: "DD/MM/YYYY - hh:mm:ss". If you cannot reach the deadline, print a single line containing the word "IMPOSSIBLE" (without quotes).
| Input Sample | Output Sample |
|
4 4 3 29/12/2015 - 20:00:00 31/12/2015 - 20:00:00 0 1 01-00-00-00 0 3 05-00-00-00 1 3 01-00-00-00 3 3 05/09/2015 - 16:30:00 06/09/2015 - 00:00:00 0 1 00-07-00-00 0 2 10-00-00-00 2 1 00-00-30-00 3 3 05/09/2015 - 16:30:00 06/09/2015 - 00:00:00 0 1 00-07-00-00 0 2 10-00-00-00 2 1 00-00-30-01 3 3 27/02/2016 - 00:00:00 01/03/2016 - 00:00:00 0 1 02-00-00-00 0 2 10-00-00-00 2 1 00-00-30-00 |
POSSIBLE 31/12/2015 - 20:00:00 POSSIBLE 06/09/2015 - 00:00:00 IMPOSSIBLE POSSIBLE 29/02/2016 - 00:30:00 |