Domino Sequence Arrangement

You are given a set of domino pieces represented as strings. Each domino is represented in the format a:b, where a and b are integers. The domino pieces are provided as a space‐separated string. Your task is to determine whether it is possible to arrange all the dominoes in such a way that the right number of one domino matches the left number of the next domino. If such an arrangement exists, output the arranged sequence (each domino printed in the same a:b format, space‐separated). Otherwise, output Invalid sequence.

This problem is equivalent to finding an Eulerian path in a directed graph. In such a path each domino corresponds to an edge and the condition on the connecting numbers corresponds to the property that the number of vertices in the resulting sequence is equal to the number of domino pieces plus one, i.e., \( |V| = |E| + 1 \).

inputFormat

Input is given via stdin as a single line string. The line contains one or more domino pieces separated by spaces. Each domino piece is formatted as a:b, where both a and b are integers.

outputFormat

Output to stdout a single line. If a valid arrangement exists, print the domino pieces in the arranged order separated by a single space. Each domino should be printed in the format a:b indicating the connection from one number to the next. If no valid domino arrangement exists, output Invalid sequence.

2:1 1:3 3:2

2:1 1:3 3:2