The Center City fire department collaborates with the transportation department to maintain maps of the city which reflects the current status of the city streets. On any given day, several streets are closed for repairs or construction. Firefighters need to be able to select routes from the firestations to fires that do not use closed streets.
Central City is divided into non-overlapping fire districts, each containing a single firestation.
When a fire is reported, a central dispatcher alerts the firestation of the district where the fire is located and gives a list of possible routes from the firestation to the fire. You must write a program that the central dispatcher can use to generate routes from the district firestations to the fires. The city has a separate map for each fire district. The input file contains several test cases representing different fires in different districts. The first line of a test case consists of a single integer which is the number of the streetcorner closest to the fire.