$\color{red}\texttt{Z}\color{orange}\texttt{B}\color{green}\texttt{O}\color{cyan}\texttt{J}\color{black}-\texttt{P1021}$

$\texttt{Play Game I}$

$\texttt{Description}$

当刷完 $\texttt{OJ}$ 上的所有题目后，理所当然的，$\color{black}\texttt{A}\color{red}\texttt{wKarLeGend}\color{black},\color{gray}\texttt{zombie462}\color{black},\texttt{K}\color{red}\texttt{evin_Wa}$就开始他们的颓废生涯了。

他们玩的是 $\texttt{Minecraft}$ 服务器上的 $\texttt{zombies}$ 游戏，又称僵尸末日。游戏的目标是打僵尸，撑过最多的回合。由于 $\color{gray}\texttt{zombie462}$ 与这个游戏心有灵犀，导致他从头至尾几乎没死过一次，而其他两个人就不一定了。一开始，$\color{black}\texttt{A}\color{red}\texttt{wKarLeGend}$（下简称 $\texttt{A}$）和 $\color{black}\texttt{K}\color{red}\texttt{evin_Wa}$（下简称 $\texttt{K}$）中的一个被击倒在了某个地方，而此时 $\color{gray}\texttt{zombie462}$（下简称 $\texttt{Z}$）在另一个地方玩耍。这时，$\texttt{Z}$ 要以最快的速度去被击倒的那个人身边去复活他。不幸的是，当 $\texttt{Z}$ 复活完一个人离开时，另一个人又会被击倒……

整个地图是一个太阳图结构。所谓太阳图，就是整张图包括一个简单环，其他各点都与环上的某个点连接有且仅有一条边。整个地图共有 $n$ 个房间，每个房间都有它自己的名字，这些房间之间有走廊可以通行，显然，走廊的数量 $m=n$。

现在，给出 $Q$ 个询问，每个询问包括两个字符串 $S$ 和 $T$，分别表示 $\texttt{Z}$ 所在的位置和 $\texttt{A}$ 或 $\texttt{K}$ 所在的位置。$\texttt{Z}$ 在一个单位时间内可以从一个房间走到另一个房间，现在请求出 $\texttt{Z}$ 至少需要多少时间才能到达 $\texttt{A}$ 或 $\texttt{K}$ 所在的房间。

$\texttt{Input Format}$

第一行一个数 $n$，表示房间数。

第二行一个数 $p$，表示环上的点的个数。

第 $3 \to 2+p$ 行，每行一个字符串 $s_i$，表示环上这个房间的名字。

第$3+p \to 2+n$行，每行一个字符串 $k_i$ 和一个整数 $r$，表示不在环上的房间的名字和它连接的房间的序号。

接下来一个数 $Q$，表示询问数。

第 $4+n \to 3+N+Q$行，每行包括两个字符串 $S$ 和 $T$，用空格隔开，分别表示 $\texttt{Z}$ 所在的位置和 $\texttt{A}$ 或 $\texttt{K}$ 所在的位置。

我们假定房间序号按读入的顺序排列，且环上的第 $i$ 个点连接第 $i+1$ 的点，特别的，第 $p$ 个点连接第 $1$ 个点。

$\texttt{Output Format}$

共 $Q$ 行，每行一个数$ans$，表示你对于每个问题的答案。

$\texttt{Sample}$

$\texttt{Input 1}$

xxxxxxxxxx
8
6
Alley
Hotel
Apartment
PowerStation
Gallery
Office
Garden 2
Roof 4
3
Apartment Apartment
Garden Roof
Alley Gallery

$\texttt{Output 1}$

xxxxxxxxxx
0
4
2

$\texttt{Input 2}$

xxxxxxxxxx
4
1
ParkEntrance
BumperCars 1
FerrisWheel 1
RollerCoaster 1
2
RollerCoaster BumperCars
ParkEntrance RollerCoaster

$\texttt{Output 2}$

xxxxxxxxxx
2
1

$\texttt{Input 3}$

xxxxxxxxxx
8
4
Mansion
GreatHall
Balcony
Library
Courtyard 1
Crypt 1
Dungeon 4
Graveyard 3
5
Crypt Crypt
Mansion Courtyard
Graveyard Library
Dungeon Graveyard
Courtyard Graveyard

$\texttt{Output 3}$

xxxxxxxxxx
0
1
2
3
4

$\texttt{Hint}$

你可以将问题归约为两点间的最短路。

样例 $2$ 的存在是为了告诉你环不一定有多个点组成。

数据规模

对于$30\%$的数据，$N\leq 100$；

对于$50\%$的数据，$N\leq 1000$；

对于$70\%$的数据，$N\leq 10^5$；

对于$100\%$的数据，$N\leq 3\times 10^5$。

对于$100\%$的数据，$1 \le P,Q\le N$。

对于全部的数据，如果标程运行时间超过 $\texttt{600ms}$，则给出 $\texttt{1500ms}$ 时限。