I think this should work:
For each List **L** of the **k** lists, lets denote this List **L** like one tuple (ui, ui + 1, ..., un) of vertices, then create one edge from ui to ui + 1.
Now after builded this graph you can run one dfs starting from each vertice (source), and in the DFS you need mark in a table **T**, let **s** be the source vertice, so for all others vertices **v** visited in the DFS mark **T[source][s] = T[s][source] = true**, this mean that you know the relative order between the two vertices. After runned the DFS over all sources loop over all pairs of vertices **(u, v)** and if **T[u][v]** is false, you need to ask the heights of **u** and **v**. 
e.g
n = 8, k = 2
**List1 = {A, C, D, E}**
**List2 = {F, G, A, B, H}**
****
**Edges = {A -> C, C -> D, D -> E, F -> G, G -> A, A -> B, B -> H}** 
So in the DFS starting in A you can mark:
T[A][C] = T[C][A] = true
T[A][D] = T[D][A] = true
T[A][E] = T[E][A] = true

Now starting from B you can mark
T[B][H] = T[H][B] = true

Now from C
T[C][D] = T[D][C] = true
T[C][E] = T[E][C] = true

repeat this process until the last vertice, and you can see that in the end:
T[A][B] = T[B][A] = false
T[A][H] = T[H][A] = false
T[C][B] = T[B][C] = false
T[C][H] = T[H][C] = false
T[D][B] = T[B][D] = false
T[D][H] = T[H][D] = false
T[E][B] = T[B][E] = false
T[E][H] = T[H][E] = false

So you need ask the heights of A, B, C, D, E, H.