P1185 Drawing a Binary Tree

A binary tree is a basic data structure. It is either empty, or consists of a root node, a left subtree, and a right subtree. The left and right subtrees are also binary trees. When a binary tree has height $m-1$, it has $m$ levels. If, in a binary tree, every level except level $m$ has the maximum possible number of nodes and all leaf nodes are on level $m$, then it is a full binary tree. Now you are required to write a program to draw a binary tree that is obtained by removing some nodes from a full binary tree. For a full binary tree, draw it according to the following rules: 1. Nodes are represented by the lowercase letter `o`. For a parent node, use `/` to connect to its left child and `\` to connect to its right child. 2. Define $[i,j]$ as the character located at row $i$ and column $j$. If $[i,j]$ is `/`, then $[i-1,j+1]$ and $[i+1,j-1]$ must be either `o` or `/`. If $[i,j]$ is `\`, then $[i-1,j-1]$ and $[i+1,j+1]$ must be either `o` or `\`. Likewise, if $[i,j]$ is a node `o` on levels $1\sim m-1$, then $[i+1,j-1]$ is `/` and $[i+1,j+1]$ is `\`. 3. For the nodes on level $m$ (the leaves): if two leaves share the same parent, they are separated by 3 spaces; if two leaves are adjacent but do not share the same parent, they are separated by 1 space. There is no space before the first (leftmost) node on level $m$. Finally, after drawing a full binary tree, delete $n$ nodes from it (each deletion removes that node, its left and right subtrees, and its connection to its parent). Replace all removed characters with spaces (the space is `ASCII 32`; outputting `ASCII 0` will be judged as a wrong answer).

The first line contains two positive integers $m$ and $n$, the number of levels of the binary tree to draw and the number of nodes to delete. The next $n$ lines each contain two positive integers, indicating deletion of the $j$-th node on level $i$.

Output the binary tree drawn according to the requirements.

30% of the testdata satisfy: $n=0$. 50% of the testdata satisfy: $2\le m\le 5$. 100% of the testdata satisfy: $2\le m\le10,0\le n\le 10,1