URI Online Judge | 2509

Latex Editor

By Hamilton José Brumatto BR Brazil

Timelimit: 1

LATEX is an excellent interpreter of formatting language for the construction of texts, articles, presentations,... To facilitate the construction of LATEX text, a specific editor is usually used. The power of language comes from the great ease of including modules and packages. One of these packages is the pstricks which together with pst-node and pst-tree allows building general trees. Our intention is to build binary trees. The following command constructs the tree in the figure:
\pstree{\Tcircle{A}}{\pstree{\Tcircle{B}}{\Tcircle{D}\Tcircle{E}}\Tcircle{C}}

In general, the \pstree{}{} command receives two arguments: the first argument is the root, necessarily a node, and the second are the child trees that can be node or tree (recursively by a command \pstree{}{}). A node is represented by the \ Tcircle {} command that will create a circle with its written argument inside it. Os filhos, precisam ser exatamente 2 (para nosso objetivo: árvore binária). Como este comando possui vários níveis de recursividade profundidade da árvore) acaba ficando confuso a contagem de parˆentesis. Uma pequena troca produz resultados inesperados. As an exemple:
\pstree{\Tcircle{A}}{\pstree{\Tcircle{B}}{\Tcircle{D}}{\Tcircle{E}}\Tcircle{C}}

You have been prompted for a program, to be embedded in a LATEX Editor, that verifies that the syntax of the pstree is correct to form binary trees.

Input

The input consists of several test cases, each test case consists of a single line with a LATEX formatting expression for constructing a binary tree using the \pstree{}{} and \Tcircle{} commands. The maximum size of the expression is 1000 characters without any whitespace being entered. As an argument of the \Tcircle{} command we always have a single character in the range 'A' to 'Z'. There is no redundancy of brackets '{' '}', only the first-level brackets that houses the arguments of each command appears.

Output

For each input test case your program should generate a single line output if the formatting expression is constructed as a binary tree, with "SIM", or "NAO" otherwise.

Input Sample Output Sample

\pstree{\Tcircle{A}}{\Tcircle{B}\Tcircle{C}}
\pstree{\Tcircle{A}}{\Tcircle{B}}{\Tcircle{C}}
\pstree{\Tcircle{A}}{\pstree{\Tcircle{B}}{\Tcircle{D}\Tcircle{E}}\Tcircle{C}}
\pstree{\Tcircle{A}}{\pstree{\Tcircle{B}}{\Tcircle{D}}{\Tcircle{E}}\Tcircle{C}}

SIM
NAO
SIM
NAO