Cross The River

Most of you may have played the game called crossing the river. This game is: a farmer carries a wolf, a sheep and a basket of grass to cross a river , but only one boat can be used . And everytime ,at most one thing and the farmer can take the boat to cross the river because only the farmer can use the boat . But if the farmer is not in, the wolf will eat the sheep ,the sheep will eat the grass . You are asked to help the farmer cross the river without losing anything . I think most of you can find the way.
But this time , the problem is more difficult . The farmer now takes more things, and some of them may eat the other thing if the farmer is not in . At the same time , the boat is becoming more bigger and it may be able to carry more things .You are asked to help the farmer to find a way to cross the river as soon as possible without losing anything.

Each test case will contain three integers n(1=<n<=11) ,m(m<=100) and t (1=<t<=5). n stands for the number of things the farmer carries , m stands for the number of dangerous condition that some things may be eaten by others ,t stands for the number of things the boat can carry besides the farmer.
Then n line follows , stands for the name of the n things . Then name will only contains lowercase letters ,and the length will not exceed 20.
Then m line follows ,each line contains several things ,which means if these things stay together without the farmer,some thing will been eaten.

For each case, output the least time the farmer needs to operate the boat in one line.If it’s impossible to cross the river without losing anything ,just output -1 in one line.

2 1 1
sheep
wolf
sheep wolf

3

Hint
At first the farmer carrys the sheep to cross the river ,then the farmer return back without carrying anything, then carrying the wolf to cross the river.

dandelion

HDU 8th Programming Contest Online