Intelligence Cloud Privacy Company (ICPC) 是一家世界著名的云服务公司，旨在为用户开发安全且强大的云计算环境。ICPC 的工程师构建了一个包含 $n$ 个计算节点的数据中心，节点编号为 $1, 2, \dots, n$，并有 $m$ 条通信链路。我们可以将该数据中心建模为无向图 $G = (V, E)$，其中 $n$ 个顶点代表 $n$ 个计算节点，如果节点 $i$ 和节点 $j$ 之间存在通信链路，则它们之间有一条边；我们也将 $i$ 和 $j$ 称为该链路的两个端点。此外，对于 $G$ 中的任意两个节点 $i$ 和 $j$，它们之间最多只有一条通信链路，且同一个节点之间不存在通信链路。

数据中心 $G$ 中的线性阵列结构（linear array structure）是一个节点序列 $\langle v_0, v_1, \dots, v_{k-1} \rangle$，其中 $k \ge 2$，使得对于 $1 \le i \le k-1$，任意两个连续节点 $v_{i-1}$ 和 $v_i$ 之间都有通信链路，且对于 $0 \le i \le k-1$，$v_i$ 互不相同。环结构（ring structure）是一个节点序列 $\langle v_0, v_1, \dots, v_{k-1} \rangle$，其中 $k \ge 4$，使得对于 $1 \le i \le k-1$，任意两个连续节点 $v_{i-1}$ 和 $v_i$ 之间都有通信链路，$v_0 = v_{k-1}$，且对于 $0 \le i \le k-2$，$v_i$ 互不相同。如果数据中心 $G$ 中任意两个节点之间都存在线性阵列，则称其为连通的；否则，称其为不连通的。利用某种优雅的资源分配算法，ICPC 的研究团队需要找到以下关键结构以增强隐私和安全性：

1. 关键节点（Critical node）：$G$ 中一个节点，移除该节点会使 $G$ 不连通。
2. 关键链路（Critical link）：$G$ 中一条通信链路，移除该链路会使 $G$ 不连通。
3. 关键组件（Critical component）：$G$ 中通信链路的一个极大集合，使得集合中的任意两条通信链路都位于同一个环上。
4. 最大关键组件（Largest critical component）：包含通信链路数量最多的关键组件。

给定一个连通的数据中心 $G$，你的任务是编写一个计算机程序来计算关键节点的数量、关键链路的数量，以及 $$\mu^* = \frac{\text{关键组件的数量}}{\text{最大关键组件中的通信链路数量}} = \frac{p}{q}$$ 其中 $\frac{p}{q}$ 是 $\mu^*$ 的最简分数形式。

输入格式

输入文件的第一行包含一个整数 $L$ ($L \le 10$)，表示测试用例的数量。对于每个测试用例，第一行包含两个整数（由空格分隔），分别表示 $n$ 和 $m$。随后紧跟 $m$ 行，每行包含两个整数，表示一条通信链路的两个端点；此外，任意两个连续的整数由空格分隔。

输出格式

每个测试用例输出一行。每行包含四个正整数，分别表示关键节点的数量、关键链路的数量、$p$ 和 $q$，其中 $\frac{p}{q}$ 是 $\mu^*$ 的最简分数形式。注意，任意两个连续的整数由空格分隔。

数据范围

• 对于每个测试用例，$3 \le n \le 1000$。
• $n - 1 \le m \le \frac{n(n-1)}{2}$。
• 所有 $L$ 个测试用例中 $m$ 的总和小于 $10^6$。

样例

样例输入 1

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

样例输出 1

0 0 1 6

样例输入 2

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

样例输出 2

2 1 1 1