{"problem":{"name":"[GDCPC 2023] Canvas","description":{"content":"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 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9697"},"statements":[{"statement_type":"Markdown","content":"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.\n\nFind the optimal order to perform the operations, so that after all operations, the sum of all elements in the sequence is maximized.\n\n## Input\n\nThere are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:\n\nThe 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.\n\nFor 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.\n\nIt's guaranteed that neither the sum of $n$ nor the sum of $m$ of all test cases will exceed $5 \\times 10^5$.\n\n## Output\n\nFor 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\n[samples]\n\n## Note\n\nFor 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$.\n\nFor 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$.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9697","tags":["图论","2023","广东","Special Judge","O2优化","图论建模","强连通分量","省赛/邀请赛"],"sample_group":[["2\n4 4\n1 1 2 2\n3 2 4 1\n1 2 3 2\n2 1 4 1\n4 2\n3 2 4 1\n1 2 3 1","7\n4 1 3 2\n5\n2 1"]],"created_at":"2026-03-03 11:09:25"}}