Switch toggling instruction

Ingrid runs a large railway station, and one of her duties is routing trains to the right platforms. The station has one entrance and many switches that send trains on to other switches and to platforms.

A switch has one inbound track and two outbound tracks. A platform has one inbound track, and the station entrance has one outbound track. Every outbound track is joined to exactly one inbound track, and every inbound track to exactly one outbound track. Every switch and every platform is reachable from the entrance.

The track at a platform is a dead end, and a train disappears from the platform as soon as it arrives.

Every morning Ingrid reads the timetable and writes a switch toggling instruction that records which switch to toggle and when. Write the program that does this for her.

The first line contains the number of switches and platforms in the station, $n$ ($3 \le n \le 51$).

The $i$-th of the next $n$ lines describes the switch or the platform with number $i$. The line starts with the character p for a platform or the character s for a switch. Then comes an integer $q_i$, the number of the switch that the inbound track is connected to, or 0 if it is connected to the station entrance ($0 \le q_i < i$). A platform line ends with one lowercase English letter, the name of the platform. All platform names are different.

A train needs exactly one minute to move between two connected switches, or between a switch and a platform. The entrance and the first switch are one minute apart as well: a train that is at the entrance at minute $a$ is at the switch connected to the entrance at minute $a+1$. In the morning every switch is set so that a train passes to the connected switch or platform with the lower number.

The next line contains the number of trains in the timetable, $m$ ($1 \le m \le 1000$). Each of the next $m$ lines contains an integer $a_i$ and a character $p_i$ ($0 \le a_i \le 10000$, $a_i > a_{i-1}$). Here $a_i$ is the minute when the train arrives at the station entrance, and $p_i$ is the name of the platform this train must reach.

On the first line print the number of commands in the instruction, $c$. Each of the next $c$ lines holds one command as two integers $s_i$ and $t_i$ ($1 \le s_i \le n$, $0 \le t_i \le 10^9$), meaning that switch $s_i$ is toggled between minute $t_i-1$ and minute $t_i$.

Exactly one instruction is accepted. Follow these rules.

• Every train reaches its destination platform.
• The number of commands $c$ is the smallest possible under that condition.
• Every command is as late as possible. A switch is toggled at the minute when the train that needs the new direction arrives at that switch.
• Commands are printed in increasing order of $t_i$, and commands with equal times in increasing order of switch number.

If no command is needed, print only 0 on the first line.