题目描述

译自 CERC 2018「H. The Lord of the Kings」

在多年与海外国家的战争后，我们的国家终于成功去除了大多数反动势力和敌人。如此光辉的胜利应该被长时间记住并庆祝。因此，我们的国王宣布将胜利日这一天定为一个公共节日，并且要举行胜利游行。在游行中，军队会跟着国王从他的宫殿出发，访问国家里的每个城市。

国王和他的随从将一种环保的电动直升机作为交通工具。这种直升机有一个缺点，就是它的航程较短。国王让你和你的顾问在一些农场和所有城市中修建停机坪，使得从他的宫殿出发，经过一些停机坪后都可以到达任何城市。然而，建停机坪和基础设施都很费钱。所以要最小化最小化停机坪的修建数量。

此外，由于直升机特殊的设计，国王和他的士兵需要以特殊的方式移动，这就会影响停机坪的数量和位置。

给你一张这个国家的矩形网格地图，其中包含代表村庄，城市和宫殿的网格。同时，也给你了直升机的移动方式——与国际象棋中「车（Rook）」、「后（Queen）」、「象（Bishop）」、「马（Knight）」或「王（King）」之一的移动方式一样（每种棋子的详细移动方式见「数据范围与提示」）。你的任务是求出最少需要在多少农场或城市修停机坪才能够满足国王的需求。国王的宫殿中已经修建了停机坪，因此不需要修一个新的了。

输入格式

第一行包含两个整数 $N,M$，表示我们的国家有 $N$ 行 $M$ 列；

第二行两个整数 $X,Y$，表示国王宫殿的位置，接着一个字符，表示移动方式（R——车，Q——后，B——象，N——马，K——王）；

第三行包含一个整数 $T$，表示国家里的城市数；

接下来 $T$ 行，每行包含两个整数 $W,Z$，表示一个城市的位置。所有城市都在不同的网格中，没有城市和宫殿位于同一格。所有既不代表城市也不代表宫殿的格子都是农场。

输出格式

输出一行一个整数，表示至少要修建多少停机坪。如果不可能使得国王和他的士兵能够到达每一个城市，输出 $-1$。

3 3
3 1 K
2
1 1
1 3

3

3 3
3 1 Q
2
1 1
1 3

2

5 5
4 4 R
4
1 2
2 1
2 5
5 1

6

数据范围与提示

$1\le N,M\le 15,1\le T\le 10,1\le X,W\le N,1\le Y,Z\le M$

下图为直升机的运输方式（同国际象棋对应棋子的行棋规则）：