Description

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).

Input Format

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 Format

Output the binary tree drawn according to the requirements.

2 0

  o  
 / \ 
o   o

4 0

           o           
          / \          
         /   \         
        /     \        
       /       \       
      /         \      
     o           o     
    / \         / \    
   /   \       /   \   
  o     o     o     o  
 / \   / \   / \   / \ 
o   o o   o o   o o   o

4 3
3 2
4 1
3 4

           o           
          / \          
         /   \         
        /     \        
       /       \       
      /         \      
     o           o     
    /           /      
   /           /       
  o           o        
   \         / \       
    o       o   o      

Hint

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<i\le m,j\le 2^{i-1}$.

Translated by ChatGPT 5