Flatten a Multi-Level Doubly Linked List

A multi-level doubly linked list is a doubly linked list where some nodes have an additional child pointer that may point to a separate doubly linked list. Your task is to flatten this list so that all the nodes appear in a single-level list following a depth-first search (DFS) order.

The flattening process works as follows: for each node encountered, first record the node’s value, then recursively process its child list (if it exists), before moving on to the next node in the same level.

The list is provided via a recursive input format (see Input Description) that encodes the multilevel structure. Once flattened, output the node values separated by a single space.

inputFormat

The input is read from standard input (stdin) and follows this recursive format:

1. The first line contains an integer n, representing the number of nodes at the current (or main) level.
2. For each of the n nodes, there is a line containing two integers: the node’s value and an integer k representing the number of children of that node.
3. If k > 0, then the definitions for these k child nodes follow immediately, each formatted in the same way recursively.

For example, a two-node list where the second node has one child is provided as:

2 1 0 2 1 3 0

If the list is empty, the input will be a single line containing 0.

outputFormat

Output the values of the flattened list to standard output (stdout) in a single line, separated by a single space. If the list is empty, output nothing.## sample

6
1 0
2 4
7 0
8 2
11 0
12 0
9 0
10 0
3 0
4 0
5 0
6 0

1 2 7 8 11 12 9 10 3 4 5 6