SP8849 IMITATE - Imitation

Iris 是一名专注于动物行为学的学生，她对动物的模仿行为特别感兴趣。模仿是动物的一种复杂行为表现，即个体通过观察并效仿他人的动作。 作为一名出色的研究者，Iris 制作了一个数学模型来刻画动物的身体形态。她将身体视为由多个关节构成，并用关节之间的有序对集合来表示动物的身体状态。为了研究模仿现象，Iris 定义了关节之间的“相关性”。这种相关性指的是将身体状态的有序对通过传递闭包进行处理，并去除自反对后的结果。换句话说，相关性是一个反自反关系。如果两个身体状态的相关性相同，则称一个身体状态在模仿另一个。 例如，对于关节集合 {J1, J2, J3}：第一个身体状态为 (J1, J2) 和 (J2, J3)，第二个身体状态为 (J1, J2)、(J2, J3) 和 (J1, J3)。根据传递闭包的定义，两个状态的相关性集合都是 (J1, J2)、(J2, J3) 和 (J1, J3)，因此可以认为第一个状态在模仿第二个状态。 给定某个身体状态，也就是一组关节间的有序对，Iris 想要找到一个模仿该状态的新身体状态。同时，这个新状态的有序对数量应该是最少和最多两种情况。你的任务是计算这两种情况下的有序对数量。

输入包括多个测试用例。第一行为一个整数，表示测试用例的数量。总共有大约 100 个测试用例，不过其中 90% 的规模较小。 对于每个测试用例，第一行包含两个整数 $N$ 和 $M$，分别代表关节的总数和给定身体状态中的有序对数量。（$1 \le N \le 1000$，$0 \le M \le 10000$） 接下来的 $M$ 行中，每行给出一个有序对 ($X_i$, $Y_i$)，其中 $X_i$ 和 $Y_i$ 是 1 到 $N$ 之间的整数。注意，关节编号为 1 到 $N$。

对于每个测试用例，输出两个整数，分别表示期望状态中的最少和最多有序对数量。两个整数之间用空格隔开。 **本翻译由 AI 自动生成**