题目描述

我们正在进行一个古老的占卜仪式。在这个仪式中，会给定一个长度为 $n$ 的序列。初始时，序列里的元素均为 $0$。

现在我们通过占卜求得了 $m$ 次操作，每次操作是一个四元组 $(l_i, x_i, r_i, y_i)$，表示把序列里第 $l_i$ 个元素改为 $x_i$，第 $r_i$ 个元素改为 $y_i$。数据保证 $x_i, y_i \in \{1, 2\}$。

根据古老的传说，在所有操作都进行完以后，序列里元素的和就是你本场模拟赛的成绩。自然，你希望这个和越大越好。

显然，进行这 $m$ 次操作的先后顺序会影响你最终所得的序列。你决定进行作弊：在真正进行这 $m$ 次操作前，对 $m$ 次操作进行重排，使得操作结束后序列里元素之和最大。

你需要输出这个最大的和，并给出一种重排的方案。

输入格式

输入的第一行是一个整数 $id$，表示当前输入数据所在的测试点编号，你可以利用这个编号来判断测试点的特殊性质。

本题单个测试点内有多组测试数据。输入的第二行是一个整数，表示数据组数 $T$。对每组数据，按如下格式输入：

第一行是两个整数，表示序列长度 $n$ 和操作个数 $m$。

接下来 $m$ 行，每行四个整数 $l_i, x_i, r_i, y_i$。

输出格式

对每组数据，输出两行：

第一行是你能得到的最大元素和。

第二行是 $m$ 个整数，$a_1, a_2, \dots a_m$ 表示最优操作顺序。其中 $a_i$ 表示你给出的重排方案里第 $i$ 次操作是输入的第 $a_i$ 个四元组。显然你的输出要保证 $1 \sim m$ 中的每个数出现恰好一次。

如果有多种能够使得和最大的方案，你可以输出任意一种。

样例

样例输入 1

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

样例输出 1

7
4 1 3 2
5
2 1

样例输入/输出 $2 \sim 8$

见下发文件 seq2.in/ans 至 seq8.in/ans。其限制满足输入的第一个数所表示的测试点编号的限制。

数据范围与提示

部分分

测试点编号	$N, M \leq$	特殊性质
$1 \sim 3$	$8$	无
$4$	$10^3$	不存在 $i \neq j$ 使得 $l_i =l_j$ 或 $l_i = r_j$ 或 $r_i = r_j$
$5$	$10^6$	$x_i = y_i = 2$
$6$		$x_i + y_i \neq 3$
$7,8$		不存在 $i \ne j$ 使得 $l_i = l_j$ 或 $l_i = r_j$
$9,10$		保证 $x_i = 1, y_i = 2$
$11,12$		保证 $y_i = 2$
$13,14$		保证不含 $x_i = y_i = 2$ 的操作
$15\sim 20$		无

对全部的测试数据，保证 $1 \leq T \leq 10^6$，$2 \leq n \leq N \leq 10^6$，$1 \leq m \leq M \leq 10^6$，$1 \leq l_i < r_i \leq n$，$1 \leq x_i, y_i \leq 2$。

评分方式

本题采用 special judge 进行评测。你的得分分为两部分：

• （40%）最大序列和
• （60%）最优方案

如果对每组数据，你输出的第一行答案均正确，可以得到当前测试点 $40\%$ 的分数。

在第一行答案正确的前提下，如果你输出的第二行答案均正确，可以得到当前测试点剩余的 $60\%$ 分数。

注意，即使你不打算完成第二行答案，你的第二行输出格式也必须是正确的，即一个长度为 $m$ 的排列，$1 \sim m$ 中的每个数字均输出一次，输出用单个空格隔开。如果你的第二行输出格式不符合要求，当前测试点可能不会得到任何分数。

提示

数据千万条，清空第一条。

清空不彻底，爆零泪两行。

清空不规范，超时总相伴。