At this moment, through out Europe, our base station numbers 1 to N are actively oper- ational through wireless channels. Immediately we require sending C secret message frag- ments from our head quarters (base station 1) to Nth base station. Germans have developed Zämmhäim a machine which jams the frequency channel between base stations after a station has sent a message fragment. In that case, the base stations must transmit using a different frequency channel for each message fragment. There are several unidirectional channels set up between base stations at this moment. We can only make arrangements to set up number of frequency channels only between two base stations. Your task is to check whether all the message fragments can be sent to the desired base station with or without increasing frequency channel between any two particular base stations. You have to give us all possible options if it is required to increase frequency channel between two stations. –End of Attachment As members of Secret Programmers Group (SPG) you are assigned to solve this problem within 5 hrs and deliver the solution directly to Colonel Al Pacheno. You have to maintain Level 3 secrecy and destroy all documents corresponding to this as soon as you deliver the solution. Input There will be multiple test cases. The first line of each test case contains three numbers N, E and C where N (0 < N < 101) represents the number of base stations, E (E < 10000) represents the number of available connections between the base stations and C (C < 2000000000) represents the number of secret message fragments that are required to send from station 1 to station N. After that, there will be E lines. Each line contains 3 numbers: b1 (0 < b1 < 101), b2 (0 < b2 < 101) and fp (0 < fp < 5001) which represent the number of frequency channels available currently from b1 to b2. Input is terminated when N = E = C = 0.
11248 – Frequency Hopping 2/2 Output For each test case, there will be one line of output. First, you have to print the case number. If it is possible to send C secret message fragments from the current status the output will be ‘possible’. Otherwise, you have to print all pairs of stations (in ascending order) if it is possible send the required message fragments by increasing the frequency channel between any one of them. If it is still impossible, you have to print ‘not possible’. Sample Input 445 125 135 245 345 445 121 135 245 341 445 121 131 241 341 000 Sample Output Case 1: possible Case 2: possible option:(1,2),(3,4) Case 3: not possible