题目描述

Kasumi 又去 CiRCLE 找可爱的女孩子们贴贴了， Arisa 很生气于是决定从家里出发去 CiRCLE 把 Kasumi 找回来。 Kasumi 得知 Arisa 从家里出发了，因此她需要在 Arisa 回到家前偷偷跑回 Arisa 家。

现在有一张 \(n\) 个结点 \(m\) 条边的无向简单连通图，通过每条边的时长为 \(1\) 分钟， Arisa 在 \(1\) 号结点， Kasumi 在 \(n\) 号结点。相遇的定义为：在同一时刻两人到达同一个结点或者同一时刻两人经过同一条边。

Arisa 需要先从 \(1\) 号结点通过一条最短路到达 \(n\) 号结点，再从 \(n\) 号结点通过一条最短路回到 \(1\) 号结点，两条最短路互相独立，且如果有多条最短路 Arisa 可以任选一条。 Kasumi 需要从 \(n\) 号结点出发到达 \(1\) 号结点，可以选择在原处停留 \(1\) 分钟或移动到相邻的结点，并且需要满足：不论 Arisa 如何移动， Kasumi 都不会与 Arisa 相遇。

如果 Kasumi 可以到达 \(1\) 号结点且到达 \(1\) 号结点的时间严格小于 Arisa 回到 \(1\) 号结点的时间，则输出 \("Kasumi"\) 以及到达 \(1\) 号结点的最短时间；否则输出 \("Arisa"\)。

输入格式

第一行输出一个正整数 \(T(1 \le T \le 10^5)\) 表示数据组数。

对于每组数据：

第一行输入两个正整数 \(n, m(2 \le n, m \le 2 \times 10^5)\)，表示无向图中点与边的数量。

接下来 \(m\) 行，每行输入两个正整数 \(u, v(1 \le u, v \le n)\)，表示无向图中的边。

数据保证 \(\sum n \le 10^6, \sum m \le 2 \times 10^6\)。

输出格式

对于每组数据，若 Kasumi 可以到达 \(1\) 号结点则输出 \("Kasumi"\) 以及到达 \(1\) 号结点的最短时间，否则输出 \("Arisa"\)。

样例输入

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

样例输出

Arisa
Kasumi 3

提示

第1个样例：

第1分钟 Arisa 既可能在2号结点又可能在3号结点，因此 Kasumi 无法移动。

第2分钟 Arisa 在4号结点，Kasumi 也在4号结点，因此 Kasumi 无法回到1号结点。

第2个样例：

第1分钟 Arisa 只可能在2号结点，因此 Kasumi 可以移动到4号结点。

第2分钟 Arisa 只可能在5号结点，因此 Kasumi 可以移动到3号结点。

第3分钟 Arisa 只可能在2号结点，因此 Kasumi 可以移动到1号结点。

第4分钟 Arisa 回到1号结点，此时 Kasumi 已经在1号结点了。

因此 Kasumi 可以在 Arisa 回到1号结点前到达1号结点，且用时为3分钟。