Genealogy Restorer Hoseok

Time limit1sMemory limit512 MB

Summary

Given each living person's known ancestor relations, reconstruct the forest of family trees and print founders plus every person's children in lexicographic order.

Level: Medium6 of 10
Topics: Graph, DFS, Topological sort, Sorting
Solved: No attempts yet

Problem

Seokho Village is home to $N$ people. The villagers of Seokho, who are extremely outgoing, live like one big family: Sangdo's father next door, Haeun's grandmother in the house behind, Yuri's mother across the river, and so on.

One day, a fire broke out in the library of Seokho Village, which has a long history, and all the genealogies burned. The village elder, Chief Daeil, said that they still had to have a genealogy, so the villagers decided to entrust the work to Hoseok, the genealogy restorer.

Hoseok wants to restore at least the genealogy of the $N$ people living together now, so he ran an investigation and recovered the names of the ancestors each person remembers. Fortunately, thanks to the clear spirit of Seokho Village, the villagers have very good memories and remember all of their ancestors perfectly. He also found out that each family takes the form of a tree rooted at one founder. Here, "ancestor" means "one's parent" together with "one's parent's ancestors".

Write a program that reports how many families existed and outputs information about each family, and help Hoseok!

Input

The first line gives $N$ , the number of people living in Seokho Village. The second line gives the names of the people living there now, in order. Every name consists of 1 to 6 lowercase English letters, and no two names are the same.

The third line gives $M$ , the number of pieces of remembered information. The following $M$ lines give memories of the form " $X$ $Y$ ", which means that $Y$ is among the ancestors of $X$ . The same piece of information is not given twice. The input contains no contradictions.

Output

On the first line, print $K$ , the number of families. On the second line, print the names of the founders of each family, separated by spaces, in lexicographic order.

From the third line onward, for each person in lexicographic order of name, print the person's name, the number of children, and the names of the children in lexicographic order, separated by spaces.

Constraints

$1 \le N \le 1{,}000$
$0 \le M \le N \times (N-1)/2$

Examples1

Example 1

Input

7
daeil sangdo yuri hoseok minji doha haeun
7
hoseok sangdo
yuri minji
hoseok daeil
daeil sangdo
haeun doha
doha minji
haeun minji

Expected output

2
minji sangdo
daeil 1 hoseok
doha 1 haeun
haeun 0
hoseok 0
minji 2 doha yuri
sangdo 1 daeil
yuri 0