{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle type\u003d\"text/css\"\u003e\r\nh1,h2,h3,h4,h5,h6{margin-bottom:0;}div.textBG p{margin: 0 0 0.0001pt;}\u003c/style\u003e\r\n\u003cp\u003e\r\n\t\u0026nbsp;\u003c/p\u003e\r\n\u003cp\u003e\r\n\t\u003cimg align\u003d\"right\" src\u003d\"http://uva.onlinejudge.org/external/104/p10410.png\" /\u003e \u003cimg align\u003d\"left\" hspace\u003d\"20\" src\u003d\"http://uva.onlinejudge.org/external/104/p10410.jpg\" vspace\u003d\"10\" /\u003e\u003c/p\u003e\r\n\u003cp\u003e\r\n\tYou have just finished a compiler design homework question where you had to find the parse tree of an expression. Unfortunately you left your assignment in the library, but luckily your friend picked it up for you. Instead of e-mailing you the parse tree so that you can rewrite the solution, your friend decides to play a practical joke and sends you just the DFS and BFS trace. Rather than try to redo the entire question you decide to reconstruct the tree.\u003c/p\u003e\r\n\u003ch3\u003e\r\n\tInput\u003c/h3\u003e\r\n\u003cp\u003e\r\n\tThe input file contains several test cases as described below.\u003c/p\u003e\r\n\u003cp\u003e\r\n\tThe first line of a input is the number \u003cb\u003en\u003c/b\u003e (1 \u0026lt;\u003d \u003cb\u003en\u003c/b\u003e \u0026lt;\u003d 1000) of nodes in the tree. The nodes in the tree are numbered 1, 2, ..., \u003cb\u003en\u003c/b\u003e. The remaining numbers are the \u003cspan data-scayt_word\u003d\"BFS\" data-scaytid\u003d\"3\"\u003eBFS\u003c/span\u003e traversal followed by the \u003cspan data-scayt_word\u003d\"DFS\" data-scaytid\u003d\"4\"\u003eDFS\u003c/span\u003e traversal. Note that when a parent was expanded the children were traversed in ascending order.\u003c/p\u003e\r\n\u003ch3\u003e\r\n\tOutput\u003c/h3\u003e\r\n\u003cp\u003e\r\n\tThe output for each case should consist of \u003cb\u003en\u003c/b\u003e lines, one for each node. Each line should start with the node number followed by a colon followed by a list of children in ascending order. If there is more than one solution, any correct answer is acceptable.\u003c/p\u003e\r\n\u003ch3\u003e\r\n\tSample Input\u003c/h3\u003e\r\n\u003cpre\u003e\r\n8\r\n4 3 5 1 2 8 7 6\r\n4 3 1 7 2 6 5 8\r\n\u003c/pre\u003e\r\n\u003ch3\u003e\r\n\tSample Output\u003c/h3\u003e\r\n\u003cpre\u003e\r\n1: 7\r\n2: 6\r\n3: 1 2\r\n4: 3 5\r\n5: 8\r\n6:\r\n7:\r\n8:\r\n\u003c/pre\u003e\r\n\u003chr /\u003e"}}]}