#207 DOM Tree

Statement

問題文の言語

다다스는 경량 웹 브라우저의 디버깅 도구를 만들고 있다. 브라우저의 HTML 파서는 문서를 읽어 이미 DOM Tree를 만들어 두었지만, 디버깅 과정에서 원래의 HTML 문자열은 사라져 버렸다.

다행히 DOM Tree의 구조와 각 노드의 정보는 온전히 남아 있다. 다다스는 이 트리를 루트부터 올바른 순서로 순회하여, 브라우저가 다시 읽을 수 있는 하나의 HTML 문자열로 복원하려고 한다.

아래 그림은 하나의 DOM Tree와 이에 대응하는 HTML 문자열의 관계를 나타낸다.

DOM Tree와 HTML의 관계

이 문제에서는 실제 HTML 문법을 단순화한다. DOM Tree의 각 노드는 다음 두 종류 중 정확히 하나이다.

태그 이름이 x이고 자식 노드가 순서대로 $v_1, v_2, \cdots, v_K$ 인 태그 노드를 생각하자.

이 노드의 HTML 표현은 먼저 여는 태그 <x>를 쓰고, $v_1, v_2, \cdots, v_K$ 의 HTML 표현을 주어진 순서대로 이어 붙인 뒤, 마지막에 닫는 태그 를 쓰는 것이다.

자식이 하나도 없는 태그 노드도 축약하지 않는다. 예를 들어 태그 이름이 p이고 자식이 없다면 HTML 표현은 항상 <p></p>이다.

텍스트 노드의 HTML 표현은 그 노드가 가지고 있는 문자열 자체이다.

이 문제에서는 속성, 이스케이프, 주석, 자동으로 삽입되는 공백, self-closing 태그 등은 고려하지 않는다.

주어진 DOM Tree의 루트는 항상 $1$ 번 노드이다. $1$ 번 노드의 HTML 표현을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

각 테스트 케이스마다 한 줄에 $1$ 번 노드의 HTML 표현을 출력한다.

#	得点	制約
1	18	각 테스트 케이스에서 $N \le 20$ . 모든 테스트 케이스에 대한 $N$ 의 합은 $500$ 이하이다.
2	27	각 테스트 케이스에서 $N \le 2\,000$ .

例 1

入力例

1
4
T h1 2 2 3
S hello
T p 1 4
S test

出力例

<h1>hello<p>test</p></h1>

$1$ 번 h1 태그의 첫 번째 자식은 hello이고, 두 번째 자식은 $3$ 번 p 태그이다. 두 자식의 표현을 이 순서대로 이어 붙이면 예제 출력이 된다.

例 2

入力例

1
6
T html 1 2
T body 2 3 5
T h1 1 4
S Hello
T p 1 6
S World

出力例

<html><body><h1>Hello</h1><p>World</p></body></html>