题目描述

Catalin 曾经画了一棵树。后来，他的弟弟把这棵树改造成了一个新的图，规则如下：

• 原树中的每条边，在新图中变成一个节点；
• 新图中的两个节点之间有边，当且仅当它们对应的两条原树边在原树中有公共端点。

这样的新图称为原树的线图。

不幸的是，原来的树已经被丢掉了。现在只给出弟弟画出的新图，请你尝试重建一棵原树。

需要注意，给出的图也可能不是任何树的线图。

任务

给定一个无向图，判断是否存在一棵树，使得给定图正好是这棵树的线图。

如果存在，请输出任意一棵这样的原树；如果不存在，输出 NU。

输入格式

第一行包含一个整数 $T$，表示测试组数。

对于每组测试数据：

第一行包含两个整数 $N,M$，表示给定图的节点数和边数。

接下来 $M$ 行，每行包含两个整数 $u,v$，表示给定图中存在一条无向边 $(u,v)$。

输出格式

对于每组测试数据：

如果不存在对应的原树，输出一行：

NU

如果存在对应的原树，先输出一行：

DA

然后输出一行整数 $E$，表示原树的节点数。

接下来输出 $E-1$ 行，每行两个整数，表示原树中的一条边。

原树节点必须编号为 $1,2,\ldots,E$。如果有多种答案，输出任意一种即可；原树节点的具体编号不重要，任意重编号后的合法答案都可以接受。

数据范围

• $1\le T\le 10\,000$；
• $1\le N\le 1000$；
• $0\le M\le \dfrac{N(N-1)}2$；
• 所有测试数据的 $N^2$ 之和不超过 $1\,000\,000$。

子任务

样例

输入

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

输出

DA
6
1 2
1 3
3 4
3 5
3 6
NU

解释

第一组测试中，输出的树有 $5$ 条边，因此它的线图有 $5$ 个节点。

例如：

• 原树边 $(1,3)$ 可以对应线图中的节点 $1$；
• 原树边 $(3,5)$ 可以对应线图中的节点 $2$；
• 原树边 $(3,4)$ 可以对应线图中的节点 $3$；
• 原树边 $(1,2)$ 可以对应线图中的节点 $4$；
• 原树边 $(3,6)$ 可以对应线图中的节点 $5$。

这些原树边之间是否有公共端点，正好对应给定图中的连边关系。

第二组测试中，给定图中节点 $3$ 是孤立点，因此它不可能是某棵树的线图。

说明

本题输出不唯一。配置到 OJ 时需要使用 Special Judge 检查输出树是否确实产生给定线图。

难度评估

估计难度：省选偏难，约 CF 2500。

线图还原树需要识别给定图是否可以分解为若干个团，这些团对应原树中的节点；两个团可以在一个割点处相交，并且一个线图节点最多属于两个这样的团。官方题解可用点双连通分量处理：检查每个点双是否为团、每个点是否属于不超过两个点双、图是否连通，然后根据团的交叠关系重建原树。算法思想不算特别长，但图论判定与构造都很容易写错，而且输出不唯一，需要严谨验证。