Tanya almost left for school when the telephone rang. It was the director of studies. She said the first three lessons that day had been cancelled because of an electricity failure. Tanya was the head girl of the class and the director of studies asked her to pass this news to her classmates.

— What shall I do? — thought Tanya, — there is almost no time! OK, now I’m going to call Lena, then Katya, then Masha. Lena will meantime call Vitya, she knows his telephone number, Vitya will call Masha. No, I’ll call Masha myself: let him better call Misha. Katya will call Natasha... No, it won’t work. They quarreled yesterday. Thus there is no time to think. I must immediately call Lena. Hit-or-miss everyone will know the news.

Tanya managed to send this message to all her classmates. But someone knew it very late and someone heard this news from several people. In the evening, Tanya decided to work out a plan of calls and not to let it ride the next time. After all, she is the head girl of the class!.. But the problem turned out to be not so easy.

Help Tanya to work out a plan of calls such that a news might be delivered to all the pupils as soon as possible. All the pupils of the class must receive the message but not more than once. It takes exactly one minute to pass the news over the telephone. At the beginning only the head girl knows the news.

To solve the problem, Tanya wrote down the list of her classmates and for each classmate the list of those whom he or she might call. You may assume that if Masha can call Katya, then Katya can call Masha, too (even if only one connection is mentioned in the list). It is known that a message can be delivered to everyone in the class through a sequence of calls.

The first line contains the number of pupils N in Tanya’s class (1 ≤ N ≤ 10). The second line contains the integer number M (0 ≤ M ≤ 45). Each of the following M lines contains a pair of pupil’s names who can call each other separated by space. The last line contains the name of the head girl. All the names in the class differ and consist of no more than 20 capital and small Latin letters.

The first line of the output should contain the time in minutes necessary to spread the news to all the class according to the suggested plan. Then there is a description of the plan. The calls that should be made simultaneously must be arranged in groups. Groups should be ordered according to the time. Each group should start with a line containing the amount of calls in the group. Each call must be described in a separate line. The description of call consists of a pair of names (who calls and whom) separated by a space.