Description

Kael’zak was the last of a bloodline of hunters, living in the depths of the Traan forest. Mundane and forlorn his life had become, after losing his family to a herd of rampaging beasts, he had forsaken his family’s hunting rituals, living on the fruit of the nearby trees. “He who consumes a beast’s food shall be hunted like a beast” his late father would say, but Kael’zak did not feel his ancestral heritage reigns anymore as he believed his bloodline to be doomed, hopelessly waiting his own eventual demise.
The night had blanketed the Traan forest, as she had done so, quotidian, in all these years of Kael’zak’s solitary life, but his heart was gripped in bitter sadness more than any of those other nights. He could find no remedy to his peculiar sadness and despair, as the morning sun would bring the 10th anniversary of his family’s demise, nonetheless, and so, he wept silently until he fell asleep.
“Kael’zak, help me,” his father screamed. He ran to the hill from the other side of which he could hear his father’s cries. From the hilltop he saw his father under a tree, being beaten by three strange humanoid creatures. But, as he tried to run toward his father, the forest was ruptured under his feet, devouring him into darkness and suffocation.
Kael’zak stood up, feeling the warmth of the sun on his body, the nightmare already fading away from his mind. His blood boiling with anger and his ears still echoing the cries of his father, he picked up his long forgotten hunting bow, hurrying to the heart of the Traan forest, where he had seen his father in the nightmare. He reached the same hill, and he, unbelievably, saw a frail female figure collapsed under the same tree, her beautiful face glowing with a white heavenly light.
“Who are you? Where am I?” she asked, as she came to, after two days of being nursed by the retired hunter.
“I am Kael’zak Silvershade, the last descendant of Iraj, the great hunter of the Traan forest,” he said, “Who are you, suddenly appearing in the forest and calling me in my dreams?”
“Someone heard my cries then,” she said as she seemed to be recovering her memories, “I am Mitra Moonface, messenger of the Lord of the Realms.”
“Lord of the Realms?” he asked.
Mitra paused for a moment and then moved her hands as if she was praying to the goddess of the moon. For a moment, Kael’zak could see her face glowing brighter than ever and her red hair floating in the air.
“Look at your left hand,” she said, stopping her prayer, and as Kael’zak was looking at the strange glittering symbols on the palm of his hand, she continued: “This is your realm’s charm.”
“Now listen carefully, Kael’zak,” she said, “the world consists of numerous realms, each with its own charm. Each being has her own realm’s charm carved into their soul, preventing them from leaving their realm. Only we of the Moonface bloodline can freely move between the realms, and we have been blessed with primordial and eternal knowledge of the realms by the Lord of the Realms to become his faithful messengers. I need you to take this message from me and deliver it to a certain realm.” She concluded, showing Kael’zak a tiny scroll.
“But,” he protested, “you said you are the only bloodline able to move between the realms, why are you asking me to deliver your message?”
“I have been rendered powerless, as you can see, and there are ways to move between the realms even for you. As I said, every realm has a unique charm, if you change your charm to that of another realm, you will vanish from this realm and you will be born anew in the other.”
“But how can I change my charm?” asked the hunter.
“There are magi of different powers that can use their incantations to change the charm carved into your soul. Each incantation can either add a symbol, remove a symbol or change a symbol to another in your charm. But, you need to be careful, if any magus uses their incantation on your charm, only magi of greater power than the previous magus can change your charm.”
“But where are these magi? Why would they help me?”
“The magi have always been here. You have met them, but you have not seen them. Now that I have enchanted your eyes with the power of Gyo, you will be able to see them, just as you are able to see your charm in your hand. The magi will ask you for a quantity of gems equal to their power, and if you provide them with the gems they will use their incantation of your charm.”
“And how can I find these magi?”
“In each realm in which you are born or reborn, you will meet a magus on each of your birthdays.”
Mitra sighed and continued: “So remember Kael’zak, on each realm you are going to meet a magus every year. Each magus can use their incantation to either add a symbol, remove a symbol or change a symbol in your charm. If a magus changes your charm in a realm, only magi of greater power will be able to change it while you are in that same realm. Each magus will ask for a number of gems equal to their power if you want them to change your charm.”
She then said: “Now I will give you the charm for all of the realms, and I will also tell you the power of the magi that you would meet in each realm in the order that they would meet you, if you were reborn in those realms. I will also tell you the charm for the realm to which you need to deliver the message. You have to find the way with the least number of incantations needed to reach that realm, and also the way back from there to this realm. For each way, you have to tell me the least number of incantations needed, and the number of gems you will need throughout the way.”
And so, Kael’zak the hunter, started to learn the arts of data structures and algorithms in order to give the correct answer to Mitra the messenger.

Input
On the first line you can read the number of realms, 𝑁, on the next 3×𝑁 lines you can read, on each first line the charm for the realm, on each second line the number of magi which Kael’zak would meet in that realm and on each third line the power of the aforementioned magi in the order that they would meet Kael’zak in the realm. On the following two lines you can read, respectively, the charm for Kael’zak’s realm and the charm for the destination realm.
Output

Samples
Input 1:
4 sitting
6
1 2 1 3 2 4 knitting 4
4 2 3 1 knowing
5
2 3 1 4 2
kneeding
4 1 3 4 2 sitting
kneeding
Input 2:
4 florida
7
4 3 2 1 2 3 4 flower 4 5 6 7 8 collapse 4
2 1 2 3 teamer
3
4 5 6 teamer
florida
Output 1:
7 19
5 13
Output 2:
IMPOSSIBLE
8 36
Notes
x Each incantation can add a symbol, for example transforming ac to abc, or remove a symbol, for example transforming abc to ac, or change a symbol, for example transforming abc to adc.
x The number of incantations needed to go from the realm A to realm B, is the minimum number of aforementioned changes needed to transform the charm of A to the charm of B. Note that each realm has a charm, and the charm is a string. For example, if A’s charm is “set” and B’s charm is “beat” the number of changes or incantations needed is 2: “set” -> “bet” -> “beat”, i.e. the edit distance from “set” to “beat” is 2.
x If a magus operates on the charm only magi of greater power can operate on the charm after that. This means that if the magi of realm A have the powers: 6 1 2 5 3 1 4, if you use the first magus you can’t use the other magi, so the wise choice is to skip the first magus. Similarly, if you use the magus with the power 5, you can’t use the magi with powers 3 and 4. In other words, for this realm the best way to use the magi is using 2nd, 3rd, 5th and 7th magi so that you can use 4 incantations. In other words, the longest increasing subsequence of the sequence of magi powers is 1 2 3 4, and has a length of 4.
x In realm A of the previous example, the most number of incantations you can have is 4. Consider another realm, realm B. Let k be the number of changes needed to transform A’s charm into B’s charm. If k is bigger than 4, then you can’t directly go from realm A to realm B, but if k is less than or equal to 4 you can directly move from realm A to realm B.
x If the number of realms is 𝑁, the maximum number of magi in a realm is 𝑀, and the maximum number of symbols in a charm is 𝑆, you should solve the whole problem in 𝑶(𝑺𝟐𝑵𝟐+𝑵𝑴𝒍𝒈𝑴).
IMPORTANT README:
x This is a group project. Groups of up to 4 people are allowed. Please note that the number of people in a group does not affect the requirements or the grading, so you’re advised to form groups of the maximum size.
x You will be graded out of 110, with 10 points being extra bonus points. (i.e. a grade of 100 is considered full score and will earn your whole group the 20% of grade in the first weight scheme)
x You will need to collaborate with your groupmates; it is recommended that you use a version control system (for example, git).
x Zip your files (do not use rar or other utilities, use zip), rename it to GroupNumber.zip and upload the zip file. (e.g. Group1.zip)
x One submission per group will be done through Canvas. x Please use the Canvas discussion board for questions.
x Your code is going to be compiled with GCC. It’s your responsibility to make sure there are no compile errors. If your code generates compile errors, you will receive no credit.