Trie Modification with Increasing Integer Sequences

You are given a rooted tree (a trie) whose edges are labeled with characters. The tree has n nodes numbered from 0 to n-1, with node 0 being the root. Each edge has a character on it which is either one of the digits from 0 to 9, a comma (','), or a missing character denoted by a question mark ('?'). It is guaranteed that the tree (when no characters are missing) was constructed by writing several strictly increasing sequences of positive integers in decimal (with no leading zeros) into a string, with adjacent integers separated by commas. In other words, each leaf of the trie corresponds to a string, and if you split this string using commas, you obtain a sequence of positive integers \(a_1, a_2, \dots, a_k\) satisfying

[ a_1 < a_2 < \dots < a_k ]

Together with the no‐leading zero rule (i.e. each number is represented as a decimal string that does not start with the character '0').

However, mischievous Tommy has already deleted some characters (replaced by '?') from some of the edges in the trie. Your task is to fill in all the missing characters so that after the modifications the trie retains its property: for every leaf, the string formed by concatenating the characters on the path from the root to that leaf can be split by commas into a list of positive integers (with no leading zeros) that is strictly increasing. If there is more than one way to fill in the missing characters, you must choose the lexicographically smallest solution. Here, lexicographical order is defined over the resulting characters (using ASCII order, so comma (',') comes before '0', which comes before '1', and so on).

Input format:

• The first line contains an integer n (number of nodes).
• The next n-1 lines each contain three tokens: an integer u, an integer v, and a character c. This denotes an edge from node u to node v labeled with character c. The character c is either one of the digits '0'-'9', a comma (','), or a question mark ('?') indicating a missing character.

Output format:

• Output exactly n-1 lines, in the same order as the input edges, where each line contains u, v and the final character on that edge after you have filled in all missing characters.

Note: A valid string (from root to a leaf) must match the following regular expression in \(\LaTeX\) format:

[ ^[1][0-9](,[1-9][0-9])*$ ]

It is guaranteed that there is at least one solution for the given input.

inputFormat

The input begins with an integer n on a single line, representing the number of nodes. The next n-1 lines each contain two integers u and v, and a character c (with no extra quotes) separated by spaces. If c is a '?' it means that the edge's character is missing and needs to be filled.

outputFormat

Output n-1 lines corresponding to the edges in the same order as given in the input. Each line must contain u, v and the final character (after filling in the missing characters) separated by a space.

sample

3
0 1 1
1 2 ?

0 1 1
1 2 0