Solution

There are very few possibilities. Choose which of Andriy's two dominoes goes to the left and which goes to the right in two ways. Each domino has two orientations, so there are only $2\cdot 2\cdot 2=8$ cases.

For each case, check that:

1. the right half of the left domino equals $l$;

2. the left half of the right domino equals $r$;

3. the new left endpoint matches neither half of Taras's domino;

4. the new right endpoint also matches neither half of Taras's domino.

Print the first case that satisfies all conditions. If none does, print $-1$.

Complexity

A constant number of cases is checked, so the time and extra memory are both $O(1)$.