双向奔赴

文件读写

• 输入文件 meet.in
• 输出文件 meet.out

限制

• 1000ms
• 512MB

题目描述

小 Y 期待了很久很久的 《黑神话悟空》 终于要发售了！ 作为高端的预售客户，小 Y 马上就可以拿到自己的游戏光盘了！ 这天一早小 Y 就接到了短信通知，说他的游戏光盘已经在派送中！ 很急！小 Y 很急！小 Y 马上就要拿到游戏光盘，马上就要打开游戏！ 于是小 Y 在快递 app 上选择了加急，并且附赠了红包，让快递员第一个给小 Y 送快递 但是这还不够！小 Y 准备照着手机 app 上快递员的地址，主动去找快递员，双向奔赴！ 小 Y 所在的城市一共有 n 个路口，由 (n-1) 条双向道路将这 n 个路口全部连通，并且每条道路的长度均相等（可以看做是 1) 而现在小 Y 家在编号为 x 的路口处，app 上显示快递员现在所在的位置是编号为 y 的路口处，他们两个都会以最快的方式朝着对方移动 现在小 Y 想知道，他们两个会在某个路口相遇，还是在某条道路上相遇？ P.S. 小 Y 和快递员的移动速度也是相等的

数据范围

对于 (20\%) 的数据保证 (2 \leq n,q \leq 10) 对于 (40\%) 的数据保证 (2 \leq n,q \leq 1000) 对于 (60\%) 的数据保证 (2 \leq n \leq 3000, 2 \leq q \leq 10^5) 对于 (100\%) 的数据保证 (2 \le n,q \le 10^5, 1 \le u,v,x,y \le n)，数据保证给出的图形成一棵树。

样例输入 1

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

样例输出 1

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

输入格式

第一行两个整数 (n,q)，表示城市中有 n 个路口，以及有 q 次询问 接下来 (n - 1) 行每行包含两个整数 (u,v) 表示编号为 u 和 v 的路口之间存在一条道路 接下来 q 行每行包含两个整数 (x,y) 表示这一次询问时小 Y 的家在路口 x，快递员的位置在路口 y

输出格式

输出共 q 行，每行包含一个答案 如果小 Y 和快递员会在路口相遇，则输出 Meet at the intersection!，如果在道路上相遇，则输出 Meeting on the road! P.S. 请注意大小写和标点符号，标点符号均为英文感叹号

国庆仿真模拟2