S 老师的礼物
题号：NC269375
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

B 同学给 S 老师一棵树作为礼物。但是，S 老师在去教室的路上不小心把它弄丢了。他很难过，但他还记得这棵树的结点数 n 和每个结点编号最小的邻居 a_1,...,a_n。你作为 B 的好朋友，需要帮助老师恢复这棵树。

你需要告诉他，给定这些信息，应该是以下哪一种情况：
  • 存在至少两棵满足条件的树
  • 该树是唯一确定的
  • 该树根本不存在（他记错了）
特别地，如果该树是唯一的，你还需要按指定要求输出这棵树。

一棵树是一个连通无向图，有 n 个结点和 n-1 条边。若 (u,v) 是树边，则称结点 u,v 为邻居。

输入描述:

输入包含多组测试数据。

第一行包含一个整数 T (1\leq T\leq 2\cdot10^5)，表示测试数据的组数。

每组测试数据的第一行包含一个整数 n (2\leq n \leq 5\cdot10^5)，表示结点数。

接下来一行包含 n 个整数 a_1,a_2,...,a_n (1\leq a_i \leq n) 其中 a_i 表示 i 的最小邻居。

保证对于所有测试数据，\sum n \leq 5\cdot 10^5。

输出描述:

对于每组测试数据，输出以下三种情况之一：

- 如果存在多棵满足条件的树，则输出 Many。

- 如果没有满足条件的树，则输出 None。 

- 否则，输出 Unique，并在接下来的 n-1 行中输出这棵树。每行输出两个整数 x,y\ (1\leq x < y \leq n)，表示边 (x,y)。你需要按照 x 从小到大、x 相同时 y 从小到大的顺序排序所有的边。所以答案是唯一确定的。
示例1

输入

复制 
3
6
3 5 1 1 2 1
5
2 1 2 3 4
4
2 3 4 2

输出

复制 
Many
Unique
1 2
2 3
3 4
4 5
None