题目描述

徐老师最近在复习博弈相关的知识

但是博弈问题总是动不动就是给俩数字，给两堆石子，给两条数轴

徐老师觉得过于无聊了，于是他开发了一种新的思路——图上博弈

徐老师在纸上随便点了 $n$ 个点，编号 $1 \sim n$ 表示这个图上的所有节点

接着随意连接了 $m$ 条边，其中第 $i$ 条双向边连接了 $u_i,v_i$ 这两个节点（保证不会有重边和自环）

接下来就到了徐老师和石老师的博弈环节，他们会按照如下步骤进行博弈

1. 徐老师 可以选择两个节点 $x,y$（$x,y$ 之间没有边），用一条双向边连接这两个节点
2. 进行连通性判定，如果 $1$ 号节点可以直接或间接的连通到 $n$ 号节点，则徐老师失败
3. 石老师 可以选择两个节点 $x,y$（$x,y$ 之间没有边），用一条双向边连接这两个节点
4. 进行连通性判定，如果 $1$ 号节点可以直接或间接的连通到 $n$ 号节点，则石老师失败

重复 $1 \sim 4$ 直到有人失败

现在徐老师想知道，在两人都足够聪明的情况下，谁会获胜？

输入格式

输入包含多组测试数据，每组测试数据独立，互不干扰

输入第一行包含一个正整数 $T$ 表示测试数据数量

对于每组测试数据：

输入第一行包含两个整数 $n,m$ 表示图上的节点数量和一开始存在的边数量

接下来 $m$ 行，每行包含两个整数 $u_i,v_i$ 表示这条边连接了这两个节点

输出格式

对于每组测试数据，如果是徐老师获胜，则输出 $Mr.Xu$，如果是石老师获胜则输出 $Mr.Shi$

数据范围

本题一共包含 $20$ 组测试数据，对于所有的数据保证：$1 \leq T \leq 10^5, 2 \leq n,m \leq 10^5, 1 \leq u_i,v_i \leq n$

特别的，对于所有数据满足：$\sum{n}, \sum{m} \leq 2 * 10^5$

其中对于部分测试数据满足以下情况

样例输入1

3
3 0
6 2
1 2
2 3
15 10
12 14
8 3
10 1
14 6
12 6
1 9
13 1
2 5
3 9
7 2

样例输出1

Mr.Xu
Mr.Shi
Mr.Xu

样例解释1

对于 $3$ 个点，一开始没有边，徐老师先手只要连接 $1-2$，会发现石老师不管连 $1-3$ 还是连 $2-3$ 都会被判定失败