Let's imagine we have a group of 26 people, and we assign to each a letter of the
standard English alphabet ABCDEFGHIJKLMNOPQRSTUVWXYZ. The group then arranges
themselves into a line, and for each pair of people we write down their
relative order. For example if they line up in standard alphabetical order, then we
would write down "clue pairs" such as "A is before B", "X is before Z", and
"G is before Q".
If everybody instead lined up in random order while your back was turned, you would still be able to recreate the order afterwards just by looking at the "clues". If clues were given to you one-by-one, you might be able to determine the original order before hearing every clue.
Given a list of clues describing the relative order of letters, give both the original random order and also the index of the first clue at which the order was fully-defined.
Input Data
First line is Q, the quantity of clues.
Q lines will then follow, each holding one clue in the format A B,
indicating that in the orignial order A comes somewhere before B.
Answer
Should consist of two space-separated values.
The first value should be i, indicating that only the first i clues
are required to fully-define the order.
The second value should be a string of letters indicating the original
defined order.
Example
The below simplified example uses an alphabet consisting only of the letters ABCD.
input data:
6
B D
C A
C B
A B
C D
A D
answer:
4 CABD
The below example uses the full standard English alphabet.
input data:
31
N C
N E
N D
N R
C E
E D
D R
R J
J P
P H
H I
I M
M K
K L
L A
A F
F Y
Y V
V G
G Q
Q S
S Z
Z U
U O
O W
W X
X T
T B
X B
W B
O B
answer:
28 NCEDRJPHIMKLAFYVGQSZUOWXTB