CF513D2 Constrained Tree

You need to find a binary tree of size $ n $ that satisfies a given set of $ c $ constraints. Suppose that the nodes of the unknown binary tree are labeled using a pre-order traversal starting with $ 1 $ . For the $ i $ -th constraint you are given two labels, $ a_{i} $ and $ b_{i} $ and a direction, left or right. In case of left direction, $ b_{i} $ is an element of the subtree rooted at $ a_{i} $ 's left child. Similarly in the case of right direction $ b_{i} $ is an element of the subtree rooted at $ a_{i} $ 's right child.

The first line of input contains two integers $ n $ and $ c $ . The next $ c $ lines contain 2 integers $ a_{i} $ , $ b_{i} $ ( $ 1

Output will be on a single line. Any binary tree that satisfies the constraints will be accepted. The tree's nodes should be printed out as $ n $ space separated labels representing an in-order traversal, using the pre-order numbers as labels of vertices. If there are no trees that satisfy the constraints, print "IMPOSSIBLE" (without quotes).

Consider the first sample test. We need to find a tree with 3 nodes that satisfies the following two constraints. The node labeled 2 with pre-order traversal should be in the left subtree of the node labeled 1 with pre-order traversal; the node labeled 3 with pre-order traversal should be in the right subtree of the node labeled 1. There is only one tree with three nodes that satisfies these constraints and its in-order traversal is $ (2,1,3) $ . Pre-order is the "root – left subtree – right subtree" order. In-order is the "left subtree – root – right subtree" order. For other information regarding in-order and pre-order, see [http://en.wikipedia.org/wiki/Tree\_traversal](http://en.wikipedia.org/wiki/Tree_traversal).