暂无测试数据。

题目背景

关于搜索。。。。。

可怜的小 $K$ 在认真的刷题，可 $TA$ 的父母却认为 $TA$ 又有网隐。所以又被羊叫兽抓住了，~~真惨啊！！！~~

题目描述

这次羊叫兽聪明了，愚蠢的手下都被电了一遍。羊叫兽还设立了多层楼的大型房间（三维地图？？？）。由于这次没有引路人了，所以呢，警察只好自己摸索了。杨叔将每层设计的都很独特。
+ 首先是监控，只要警察走到了监控的**上下左右**四个方向杨叔就会多派出一名手下守在本层出口（期间不要时间===杨叔也是厉害===）。
+ 其次是关于滑动式挡板，每奇数个单位的时间里，挡板会关上，否则打开。这时警察可以选择绕路或者等待。
+ 接着就是按钮机关。警察到了某一扇联通门后，必须派遣一位警察前往最近的开门按钮才行（十分注意：没到门边上您绝对不能派遣其他警察去按按钮！！！——这是规矩QWQ）。
+ 然后就是干掉一个杨叔手下（还好警察厉害——一个单位的时间干掉一个。。。）。
+ 关于上楼，只要到了楼与楼连接点就相当于到了那一层。

输入

输入一个数 $N$ 表示 $N$ 层楼。
表示接下来每行（共 $N-1$ 行）一个 ${x_i},{y_i}$。 ${x_i}$ 与 ${y_i}$ 表示楼层 $i$ 与 楼层的连接点是 $({x_i},{y_i})$ 点。
接着输入一个数 $Q$ 表示 $Q$ 监控个数。

数据范围

矩阵边长 , 楼层 , $Q$ $\le 20$