### Woburn Challenge 2018-19 Round 4 - Senior Division

## Problem 1: World of StarCraft

Billy, the king of video games, is (among other things) a top professional *StarCraft II* player. In light of his recent success as the only human to defeat the fearsome AlphaStar AI, he has received exclusive access to play the upcoming installment in the series, *World of StarCraft*. In a natural progression for the series, this is a massively multiplayer online role-playing game.

*World of StarCraft* features `N` (2 ≤ `N` ≤ 100,000) planets, numbered from 1 to `N`. Each planet is under the control of one of three races (Protoss, Terran, or Zerg), with the character `R _{i}` representing planet

`i`'s race (either "

`P`

" for Protoss, "`T`

" for Terran, or "`Z`

" for Zerg).There are `M` (0 ≤ `M` ≤ 100,000) space routes running amongst the planets, with the `i`-th space route allowing one to travel in either direction between planets `A _{i}` and

`B`(1 ≤

_{i}`A`,

_{i}`B`≤

_{i}`N`,

`A`≠

_{i}`B`). There may be multiple space routes connecting a single pair of planets.

_{i}Despite its secretive and unreleased development status, *World of StarCraft* somehow already has an enormous player-base. Billy himself has `K` (1 ≤ `K` ≤ 100,000) friends in the game. His `i`-th friend is currently on planet `X _{i}`, and would like to reach a different planet

`Y`to complete an objective (1 ≤

_{i}`X`,

_{i}`Y`≤

_{i}`N`;

`X`≠

_{i}`Y`).

_{i}When a player is on a planet `i`, they may travel along a space route to another planet `j`, assuming that a space route exists which connects planets `i` and `j`. However, due to open hostilities amongst the three races, it's only safe to do so if both planets are under the control of the same race (in other words, if `R _{i}` =

`R`).

_{j}Billy would love to help all of his friends complete their objectives, but not without putting their in-game lives at risk! Help him determine how many friends i he has such that it's possible to safely travel through a sequence of planets beginning at planet `X _{i}` and ending at planet

`Y`.

_{i}### Subtasks

In test cases worth 8/14 of the points, `N` ≤ 1000, `M` ≤ 1000, and `K` ≤ 1000.

### Input Format

The first line of input consists of three space-separated integers, `N`, `M`, and `K`.

The next line consists of characters, `R`_{1..N}.

`M` lines follow, the `i`-th of which consists of two space-separated integers, `A _{i}` and

`B`, for

_{i}`i`= 1..

`M`.

`K`lines follow, the

`i`-th of which consists of two space-separated integers,

`X`and

_{i}`Y`, for

_{i}`i`= 1..

`K`.

### Output Format

Output a single integer, the number of friends who can safely complete their objectives.

### Sample Input

6 7 3 PZZPPP 1 2 6 4 3 4 2 5 5 6 1 4 4 2 6 4 2 3 1 5

### Sample Output

2

### Sample Explanation

Billy's first friend can safely travel directly from planet 6 to planet 4 to complete their objective.

Billy's second friend may never safely reach planet 3.

Billy's third friend can safely travel through the sequence of planets 1 → 4 → 6 → 5.

All Submissions

Best Solutions

**Point Value:** 10 (partial)

**Time Limit:** 3.00s

**Memory Limit:** 128M

**Added:** Mar 22, 2019

**Author:** SourSpinach

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...