Orange mood
Orange mood
Once the club president of the European level, "Nader" has announced that from next season, the Dutch coach who has won the respect of fans, can replace less successful Italian. When I heard about it, outraged fans of the club went to the palace of the president, in order to perpetrate an orange (the color of the Dutch national team shirts) revolution and return to the coach. It turned out that the Presidential Guard also rooting for "Nadir"...
The president is in the palace, which consists of many rooms and corridors connecting them. Two different rooms can be connected by no more than one corridor. At both ends of each corridor is a door. Some doors have a deadbolt that can lock or unlock from inside the room. Locked deadbolt locks access to the room from the corridor. Through some of the rooms (inputs) to the palace can be reached from the outside.
Initially, all doors are open. Your task is to determine whether the president to choose a room to shelter from outraged fans, so that, starting from the room, he could walk the corridors of the palace, close the door part and then go back to their hideout so that access to him outside the palace was closed.
Input
The firstline containsthree integersN, M, P -number of roomsof the palace, the numberofcorridors andentrancesto the palace (1 ≤ N ≤ 10000, 0 ≤ M ≤ 1000000, 1 ≤ P ≤ N). The second linecontains thenumbersP-numberof roomsthrough which you canget into the palace.The followingMlinesdescribes thecorridorsof the palace.Eachcorridoris definedby a pairof integers from1 toN - number ofroomsit connects.
NextN linesareinthe description ofrooms -the number ofPi -Piandthe numberof numbers- numbers ofcorridors, a doorwhichcan be lockedwhile in theroom (0 ≤ Pi ≤ 100). Roomsand corridorsare numberedby integers, startingwithunits intheirorder of appearancein the input file.
Output
In the outputfileyou want to displaya single number- the number ofrooms of the palacein whichthe presidentcan escape.Ifthese numberssomewhat, to bringthe smallestof them.If youcan nothide, to withdrawthe phrase"Impossible" (no quotes).
Sample 1 4 3 1 1 1 2 2 3 3 4 0 0 1 2 0 Sample 2 4 3 2 1 2 1 2 2 3 3 4 0 0 1 2 0
Sample 1 3 Sample 2 Impossible