最佳选手

Problem Description

第17届 Culinary Combat Professional Contest (CCPC) 已经结束，赛事组织者将选出本次比赛的最佳选手。 共有 $n$ 名选手，编号从 $1$ 到 $n$，一共进行了 $m$ 场 1 vs 1 的对决：

• 第 $i$ 场对决的是选手 $a_i$ 和 $b_i$；
• 每场对决分为上半场和下半场：
• • 在对决的上半场，选手 $a_i$ 的得分为 $x_i$，选手 $b_i$ 的得分为 $y_i$；
• • 在对决的下半场，选手 $a_i$ 和 $b_i$ 的准确得分未知，但两者得分之和为 $z_i$；
• • 选手在整场对决中的得分等于上半场得分与下半场得分之和。换句话说，在第 $i$ 场对决中，$a_i$ 和 $b_i$ 的可能得分分别为 $x_i + p_i$ 和 $y_i + q_i$，其中 $0 \leq p_i,q_i \leq z_i, p_i + q_i = z_i$。 注意，所有得分均为 非负整数 ，并且每位选手至少参加了一场对决。 定义一位选手的关键对决为：这位选手参加的对决中，得分 最小 的对决； 一位选手的最终得分为：其在关键对决中获得的得分。如果一名选手的最终得分 严格大于 所有其他选手的最终得分，则该选手将获得最佳选手奖。 由于 $m$ 场对决下半场得分的不确定，最佳选手也可能不同。请找出所有可能成为最佳选手的选手。

Input

输入包含多组测试数据。 第一行包含一个整数 $T$ ($1\leq T\leq 2 \times 10^5$)，表示测试数据的组数。 对于每组测试数据： 第一行包含两个整数 $n$, $m$ ($2 \leq n \leq 10^6$, $\lceil \frac{n}{2} \rceil \leq m \leq 10^6$)，表示选手数和对决数。 接下来的 $m$ 行，第 $i$ 行包含五个整数 $a_i$, $b_i$, $x_i$, $y_i$, $z_i$ ($1 \leq a_i, b_i \leq n$, $a_i \neq b_i$, $0 \leq x_i, y_i, z_i \leq 10^9$)，具体含义见题面。保证每位选手至少参加了一场对决。 保证所有测试数据中 $n$ 的总和 与 $m$ 的总和 都不超过 $10^6$。

Output

对于每组测试数据： 第一行输出一个整数 $k$，表示可能成为最佳选手的选手数量。 第二行输出 $k$ 个整数，按 升序 输出所有可能成为最佳选手的选手编号。特别地，当 $k=0$ 时，输出一个空行。

Sample Input

3
3 2
1 2 2 3 3
2 3 6 7 1
3 2
1 2 2 3 3
2 3 6 7 2
3 2
1 2 2 3 6
2 3 7 7 2

Sample Output

1
3
1
3
3
1 2 3

Hint

对于第三组测试数据，$3$ 名选手都有可能成为最佳选手。选手 $1$ 只有在如下情况中才能成为最佳选手：

• 在第一场对决中，选手 $1$ 得分为 $2 + 6 = 8$，选手 $2$ 得分为 $3 + 0 = 3$；
• 在第二场对决中，选手 $2$ 得分为 $7 + 2 = 9$，选手 $3$ 得分为 $7 + 0 = 7$。 在这种情况下，选手 $1$ 的最终得分为 $8$，选手 $2$ 的最终得分为 $\min(3, 9) = 3$，选手 $3$ 的最终得分为 $7$，因此选手 $1$ 为最佳选手。

Source

2024“钉耙编程”中国大学生算法设计超级联赛（9）