题目描述

There is a sequence of length $n$. At the beginning, all elements in the sequence equal to $0$. There are also $m$ operations, where the $i$-th operation will change the value of the $l_i$-th element in the sequence to $x_i$, and also change the value of the $r_i$-th element in the sequence to $y_i$. Each operation must be performed exactly once.

Find the optimal order to perform the operations, so that after all operations, the sum of all elements in the sequence is maximized.

输入格式

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($2 \leq n, m \leq 5 \times 10^5$) indicating the length of the sequence and the number of operations.

For the following $m$ lines, the $i$-th line contains four integers $l_i$, $x_i$, $r_i$ and $y_i$ ($1 \leq l_i<r_i \leq n$, $1 \leq x_i,y_i \leq 2$) indicating the $i$-th operation.

It's guaranteed that neither the sum of $n$ nor the sum of $m$ of all test cases will exceed $5 \times 10^5$.

输出格式

For each test case, first output one line containing one integer, indicating the maximum sum of all elements in the sequence after all operations. Then output another line containing $m$ integers $a_1, a_2, \cdots, a_m$ separated by a space, indicating the optimal order to perform the operations, where $a_i$ is the index of the $i$-th operation to be performed. Each integer from $1$ to $m$ (both inclusive) must appear exactly once. If there are multiple valid answers, you can output any of them.

题目大意

【题目描述】

有一个长度为 $n$ 的序列，一开始序列中的所有元素均为 $0$。另外还有 $m$ 个操作，其中第 $i$ 个操作会将序列中第 $l_i$ 个元素的值改为 $x_i$，以及将序列中第 $r_i$ 个元素的值改为 $y_i$。每个操作必须恰好执行一次。

求执行操作的最优顺序，使得所有操作执行完成后，序列中所有元素之和最大。

【输入格式】

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入两个整数 $n$ 和 $m$（$2 \leq n, m \leq 5 \times 10^5$）表示序列的长度和操作的个数。

对于接下来 $m$ 行，第 $i$ 行输入四个整数 $l_i$，$x_i$，$r_i$ 和 $y_i$（$1 \leq l_i<r_i \leq n$，$1 \leq x_i,y_i \leq 2$）表示第 $i$ 个操作。

保证所有数据 $n$ 之和与 $m$ 之和均不超过 $5 \times 10^5$。

【输出格式】

每组数据首先输出一行一个整数，表示执行操作后，所有元素的最大和。接下来输出一行 $m$ 个由单个空格分隔的整数 $a_1, a_2, \cdots, a_m$ 表示执行操作的最优顺序，其中 $a_i$ 表示第 $i$ 次执行的操作的编号。从 $1$ 到 $m$ 的每个整数（含两端）必须恰好出现一次。若有多种合法答案，您可以输出任意一种。

【样例解释】

对于第一组样例数据，按 $4, 1, 3, 2$ 的顺序执行操作后，序列变为 $\{2, 2, 2, 1\}$，元素之和为 $7$。

对于第二组样例数据，按 $2, 1$ 的顺序执行操作后，序列变为 $\{2, 0, 2, 1\}$，元素之和为 $5$。

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

7
4 1 3 2
5
2 1

提示

For the first sample test case, after performing operations $4, 1, 3, 2$ in order, the sequence becomes $\{2, 2, 2, 1\}$. The sum of all elements is $7$.

For the second sample test case, after performing operations $2, 1$ in order, the sequence becomes $\{2, 0, 2, 1\}$. The sum of all elements is $5$.