问题 4575 --C、百变小樱

4575: C、百变小樱

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

有一种关于小樱的游戏,玩家控制小樱进入迷宫中消灭塔罗牌的妖魔救心爱的小狼。
妖魔都住在一棵树的节点上,每个节点住着一个妖魔,如图所示:

小樱消灭妖魔的步骤如下:

1、   小樱先进入根节点房间。

2、   如果进入的房间存在妖魔,小樱会用一次她的魔法将妖魔消灭。

3、   如果小樱所在的房间的子节点存在妖魔,则她选择最靠近左边的房间进入。

4、   循环该过程,直到将所有房间的妖魔都消灭,退出游戏。

 

这个游戏结束后,将得到一个拿到塔罗牌顺序的日志,格式如下:、

"xiaoyu(xiaoyuan(xiaoli,xiaoben),xiaojun,xiaocc)"

 

由于该格式很难理解,所以,请你把该游戏日志描述为一个更容易理解的格式:

1、  总共有多少个妖魔。

2、  列出妖魔的名字。(按小樱找到妖魔的顺序)

3、  小樱消灭妖魔所走的路径。(如图所示,按先后顺序将妖魔编号)

输入

第一行有一个数字T(T<=20),表示总共T组测试数据。

后面有T行,每行有一个字符串,表示每次游戏的日志。

迷宫最多由50000个房间组成,妖魔的名字最多10个字符,游戏日志最多1000000个字符。

游戏日志仅由小写字母,‘(’,‘)’,或‘,’组成。

输出

对于每组测试数据,输出一个新的游戏日志:

第一行一个数字N表示总共有N个妖魔。

后面N行表示每个妖魔的名字。(按小樱找到妖魔的先后顺序)

后面2(N-1)行,每行两个数字,表示小樱所行走的路径。(如图所示,按先后顺序将妖魔编号)

两组输出数据之间有一个空行。

样例输入

3
xiaoyu(xiaoyuan(xiaoli,xiaoben),xiaojun,xiaocc)
liuxiaojia
xiaoma(huidan(xiaoxian))

样例输出

6
xiaoyu
xiaoyuan
xiaoli
xiaoben
xiaojun
xiaocc
1 2
2 3
3 2
2 4
4 2
2 1
1 5
5 1
1 6
6 1

1
liuxiaojia

3
xiaoma
huidan
xiaoxian
1 2
2 3
3 2
2 1

来源

[提交][状态]