#2191. 徐老师的双向奔赴

徐老师的双向奔赴

题目描述

徐老师期待了很久很久的 《黑神话悟空》 终于要发售了!

作为高端的预售客户,徐老师马上就可以拿到自己的游戏光盘了!

这天一早徐老师就接到了短信通知,说他的游戏光盘已经在派送中!

很急!徐老师很急!徐老师马上就要拿到游戏光盘,马上就要打开游戏!

于是徐老师在快递 appapp 上选择了加急,并且附赠了红包,让快递员第一个给徐老师送快递

但是这还不够!徐老师准备照着手机 appapp 上快递员的地址,主动去找快递员,双向奔赴!

徐老师所在的城市一共有 nn 个路口,由 n1n-1 条双向道路将这 nn 个路口全部连通,并且每条道路的长度均相等(可以看做是 11)

而现在徐老师家在编号为 xx 的路口处,appapp 上显示快递员现在所在的位置是编号为 yy 的路口处,他们两个都会以最快的方式朝着对方移动

现在徐老师想知道,他们两个会在某个路口相遇,还是在某条道路上相遇?

P.S. 徐老师和快递员的移动速度也是相等的

输入格式

第一行一个整数 nn,表示城市中有 nn 个路口

接下来 n1n - 1 行每行包含两个整数 u,vu,v 表示编号为 uuvv 的路口之间存在一条道路

接下来一行一个整数 qq 表示询问次数

接下来 qq 行每行包含两个整数 x,yx,y 表示这一次询问时徐老师的家在路口 xx,快递员的位置在路口 yy

输出格式

输出共 qq 行,每行包含一个答案

如果徐老师和快递员会在路口相遇,则输出 Meet at the intersection!,如果在道路上相遇,则输出 Meeting on the road!

P.S. 请注意大小写和标点符号,标点符号均为英文感叹号

数据范围

对于 20%20\% 的数据保证 2n,q102 \leq n,q \leq 10

对于 40%40\% 的数据保证 2n,q10002 \leq n,q \leq 1000

对于 60%60\% 的数据保证 2n3000,2q1052 \leq n \leq 3000, 2 \leq q \leq 10^5

对于 100%100\% 的数据保证 2n,q105,1u,v,x,yn2 \le n,q \le 10^5, 1 \le u,v,x,y \le n,数据保证给出的图形成一棵树。

样例输入1

4 
1 2
2 3
2 4
3
1 2
1 3
1 4

样例输出1

Meeting on the road!
Meet at the intersection!
Meet at the intersection!