10565 - HTML tag generator   

Description

小傑這學期修了太多課,每天都在和deadline賽跑,雖然他在競程基礎班學到了一個實用的方法可以幫助他從每個作業的deadline以及完成每個作業的所需時間決定出可以完成最多作業的排程方式,但是經過精密的計算,小傑發現他每次都必須放棄Web程式設計課程的作業。好不容易才選上的課程,說什麼他也不想二退,但是如果不放棄這門課的作業,其他科目就會非常悲劇。
身為小傑最佳損友的你,非常了解他每次寫網頁要花很多時間的原因,就像寫C語言時常常會因為括號沒配對好而發生compile error的悲劇一樣,他每次總是會因為幾個標籤沒配對好而辛辛苦苦地在400多行的網頁原始碼尋尋覓覓。小傑的生日就在5月5日,剛好你手頭很緊沒有錢可以買一支新的釣竿送他,因此你決定做一個可以幫助他開發HTML網頁的程式當作他的生日禮物。

 
一個以HTML語言撰寫而成的網頁原始碼會包含許多標籤,這些標籤是成對的。(在這裡我們不考慮某些不用成對表示的情況)
成對的標籤分為開始標籤與結束標籤,開始標籤必須排列在結束標籤之前,開始標籤的格式以 <標籤名稱> 表示,而結束標籤則是以 </標籤名稱>  表示。
例如以abc為名稱的成對標籤為 <abc></abc>。
 
任一組開始標籤與結束標籤之間可以包含多組成對的標籤,以下是一個合法的範例,在<abc></abc>之間包含了三組成對的標籤:
<abc><a></a><b></b><c></c></abc>
 
底下給出一些不合法的範例:
1.標籤沒有成對
<abc><abc>
2.標籤雖然成對出現,但由成對的標籤之間包夾的標籤並不成對
<a><b></a></b>

Input

本題有多組測資。

每組測資的第一行會給定正整數N (1 ≦ N ≦ 10000)。
接下來會有N行,每一行依序給出一個字串s、一個正整數id、一個正整數p,每一行都是一組成對標籤的資訊。s,id,p之間會以一個空白字元分隔。
s表示標籤的名稱,只會包含小寫英文字母,且長度不超過20個字元。
id表示該組標籤的編號(2 ≦ id ≦ N+1),每組標籤的編號是唯一的。
p表示直接包含此組標籤的標籤編號(1 ≦ p ≦ N+1)。

註1:編號為1的標籤是預設的,不會在input中出現,名稱為"html"(不含雙引號)。
註2:關於直接包含。以<a><b><c></c></b></a>為例,<c></c>被<b></b>直接包含,而不是被<a></a>直接包含。因為我們有<c></c>被<b></b>包含,且<b></b>被<a></a>包含,經過兩層以上的包含就不算直接包含,但是仍有<c></c>被<a></a>包含的關係。

Output

輸出正確的標籤排列方式。相鄰測資之間請輸出一個換行字元隔開。
正確的標籤排列方式應符合以下四點:
1.與input描述的標籤之間的包含關係一致
2.不論是開始標籤或是結束標籤,每個標籤占一行
3.若標籤S被k組標籤所包含(不一定要直接包含),則在輸出標籤S之前要先輸出3*k個空白字元
4.若有多組標籤同時被同一個編號的標籤直接包含,則這些標籤的輸出順序應和input的出現順序一致。

以下以第二組Sample為例進行解說:
<style>、</style>、<head>、</head>、<body>、</body>因為被<html></html>包含,因此在輸出標籤之前要輸出3個空格字元;
<title>、</title>因為被<html></html>以及<head></head>包含,因此在輸出標籤之前要輸出6個空格字元;
<ul>、</ul>因為被<html></html>以及<body></body>包含,因此在輸出標籤之前要輸出6個空格字元;
<li>、</li>因為被<html></html>以及<body></body>以及<ul></ul>包含,因此在輸出標籤之前要輸出9個空格字元。
<html></html>同時包含了編號為2,3,4的標籤,標籤的輸出順序是按照input的順序排列(和編號無關)。

:受限於OJ顯示Sample Output的機制(無法於行首顯示多個半形空白字元),因此Sample Output都是顯示全形的空白字元,但正確的輸出都是半形的空白字元,也就是字元' '(ASCII十進制編碼32)。

Sample Input  Download

Sample Output  Download

Tags




Discuss