P7068 [NWRRC 2014] Instruction

英格丽德是一家大型火车站的站长，除其他职责外，还负责将火车开到正确的站台。车站有一个入口，有许多道岔将列车引导至其他道岔和站台。 每个道岔有一条入站轨道和两条出站轨道，站台有一条入站轨道，车站入口有一条出站轨道。每个出站磁道连接到一个入站磁道，反之亦然。每个道岔和站台都可以从车站入口到达。 月台有一个铁路死胡同，你可以假设火车到达月台后立即从月台上消失。 每天早上，英格丽德都会查看时间表，并编写切换指令：何时以及切换哪个开关。她希望将此过程自动化以节省大量时间。

输入文件的第一行包含一个整数n—站点上交换机和平台的总数 以下n行的第i行描述了具有索引i的交换机或平台。说明以字符p开头表示平台，以字符s开头表示交换机。下一个数字q`i`表示入站轨道连接到的道岔的编号，如果连接到车站入口，则表示0(0≤q$i$≤i)平台说明还包含一个唯一的小写英文字母 -- 平台标识符。 列车在两个相连的道岔或道岔与站台之间移动只需一分钟。早上，每一个道岔都会以一种方式进行切换，列车将通过连接到道岔/站台的两条出站轨道中编号较低的一条。 输入文件的下一行包含一个整数m(0≤m≤1000) -- 时刻表上的列车数量。 以下m行中的每一行都包含整数a*i* (0≤a$i$ ≤10000;a$i$>a$i-1$) -- 列车到达车站入口的时间（以分钟为单位），以及字母p*i* -- 列车目的站台的标识符。

在第一行输出整数c中，开关切换指令中的命令数。对于每个命令，输出两个整数 s`i`和 t$i$ (1≤s$i$ ≤n;0≤ t$i$ ≤10^9) -- 开关的编号和切换开关的时间。假设开关在分钟之间切换 t$i$-1 和 `t`。 按非递减时间顺序输出命令。命令的数量不应超过100000。

Below is the time trace for the first example.  Time limit: 2 s, Memory limit: 256 MB.