Similar Cities

In SBP (the Super Rich Country) there are a great many cities. Every city contains houses, shops, and exactly one town hall. SBP is a very orderly country, so every city has a degree. A degree of $k$ means that exactly $k$ one-way roads leave every building, numbered $0$ through $k-1$.

Paths that start at the town hall are especially important. Such a path is described by the sequence of road numbers taken along the way. For example, the path described by the sequence $103$ is walked like this:

1. Start at the town hall. Take the road numbered $1$, arriving at building $X$.
2. Take road number $0$ from $X$ to building $Y$.
3. Take road number $3$ from $Y$ to building $Z$.
4. The path ends at building $Z$, which may be a house, a shop, or the town hall.

You are given the road layouts of two cities that share the same degree $s$. Find the shortest sequence that, in one of the two cities, describes a path from the town hall to a house, while in the other city it describes a path from the town hall to a building that is not a house (a shop or the town hall). In other words, find the shortest sequence for which the two cities disagree on whether the walk ends at a house.

Each road number is a single digit from $0$ to $s-1$ (note $s \le 10$), so a sequence is written as its road numbers joined together with no separators.

The first line contains the number of test cases $T$ ($1 \le T \le 20$). Each test case is given as follows.

The first line of a test case has five integers $n_1$, $d_1$, $n_2$, $d_2$, $s$ ($3 \le n_1, n_2 \le 1000$, $0 < d_1 \le n_1 - 2$, $0 < d_2 \le n_2 - 2$, $1 \le s \le 10$): the number of buildings in the first city, the number of houses in the first city, the number of buildings in the second city, the number of houses in the second city, and the degree shared by both cities.

In each city the town hall is building $0$, the houses are buildings $1$ through $d$, and the shops are buildings $d+1$ through $n-1$.

The next $n_1$ lines describe the first city: line $i$ (counting buildings from $0$) contains $s$ integers in the range $0$ to $n_1 - 1$, the destinations of roads $0, 1, \dots, s-1$ leaving building $i$. The following $n_2$ lines describe the second city in the same way. Several roads may connect the same pair of buildings, and a road may start and end at the same building.

Print $T$ lines; the $i$-th holds the answer for the $i$-th test case. If no valid sequence exists, print a single $0$. Otherwise print the length of the shortest valid sequence, then a single space, then the sequence itself. If several shortest sequences exist, print the lexicographically smallest one (the one that would come first in a dictionary).