Ideas

A unique feature of ideas is that they are not consumed when they are used: a good idea can benefit arbitrarily many people without losing its value, and it can even inspire people to derive better ideas. Each person builds on a specific set of ideas to create new ones.

To share ideas, people are connected by a worldwide network of one-way tubes. Curious creatures called packets travel through the tubes carrying ideas from one person to another; because the tubes are unidirectional, each person may have any number of incoming and outgoing tubes. Every packet starts at person $0$ and repeatedly follows this algorithm:

1. Learn and remember every idea created by the current person.
2. If the current person has no outgoing tube, stop.
3. Otherwise pick an arbitrary outgoing tube and travel through it to a new person.
4. Tell that new person all of the ideas it needs from other people.
5. Return to step 1.

Each person needs a certain set of ideas (which it must be told on arrival) and creates a certain set of ideas (which it teaches to every packet that visits it). The same idea is never both needed and created by one person, although several people may independently create the same idea.

The input guarantees that a packet can reach every person from person $0$, and that whenever a person $P$ needs an idea, every path a packet could take to reach $P$ has already visited someone who creates that idea.

To reduce the load on a packet, you want to minimize how many ideas it carries at any moment by having it forget ideas while passing through certain tubes. You must still guarantee that, no matter which path the packet takes, every time it arrives at a person it already knows all of the ideas that person needs. For each tube, determine the smallest set of ideas the packet must be carrying while it travels through that tube. This minimal set is uniquely determined.

The first line contains the number of test cases. Each test case begins with a line containing three integers $N$, $M$, and $I$ — the number of people, tubes, and ideas — each between $1$ and $1000$ inclusive. People are numbered $0$ to $N-1$ and ideas $0$ to $I-1$, and every packet starts at person $0$.

Then follow $2N$ lines, two for each person in order from $0$ to $N-1$. For person $p$, the first of its two lines lists the ideas $p$ needs and the second lists the ideas $p$ creates, given as space-separated integers; either line may be empty. No idea appears on both lines of the same person.

Finally, $M$ lines follow, each containing two integers: the source and the destination person of one tube.

For each test case, output $M$ lines, one per tube in the same order as the input. Each line lists, in increasing order, the ideas in the minimal set the packet must carry while travelling through that tube. If that set is empty, output an empty line.