CF1215F Radio Stations

除了关于照明的投诉外，Bertown 市政厅最近还收到了大量关于无线电信号覆盖不足的投诉。市长收到了 $n$ 份投诉，这些投诉内容惊人地相似：在第 $i$ 份投诉中，一位无线电爱好者提到，两个无线电台 $x_i$ 和 $y_i$ 的信号未能覆盖城市的某些区域，并要求至少有一个电台的信号能够覆盖整个城市。 当然，Bertown 的市长正在努力解决这些投诉。市里新安装了一座无线电塔，可以发射任意整数功率 $1$ 到 $M$（我们用 $f$ 表示信号功率）。市长决定选择一些无线电台，并与每个被选中的电台签订合同。要与第 $i$ 个电台签订合同，需满足以下条件： - 信号功率 $f$ 不小于 $l_i$，否则第 $i$ 个电台的信号无法覆盖全城； - 信号功率 $f$ 不大于 $r_i$，否则信号会被未与第 $i$ 个电台签约的其他城镇居民接收到。 这些信息已经让市长意识到选择电台的难度。但在咨询专家后，他得知有些电台之间的信号会互相干扰：有 $m$ 对电台（$u_i$，$v_i$）使用相同的信号频率，对于每一对，无法同时与这两台电台签订合同。如果电台 $x$ 和 $y$ 使用相同频率，$y$ 和 $z$ 也使用相同频率，并不意味着 $x$ 和 $z$ 也使用相同频率。 市长觉得分析这个问题非常困难，于是雇佣了你来帮忙。你需要选择一个信号功率 $f$ 和一组电台签约，使得： - 所有投诉都被满足（即对于每个 $i \in [1, n]$，城市至少与电台 $x_i$ 或 $y_i$ 中的一个签约）； - 选中的电台之间没有互相干扰（即对于每个 $i \in [1, m]$，城市不会同时与 $u_i$ 和 $v_i$ 签约）； - 对于每个被选中的电台，信号功率 $f$ 满足其要求（即对于每个被选中的电台 $i$，有 $l_i \leq f \leq r_i$）。

第一行包含 $4$ 个整数 $n$、$p$、$M$ 和 $m$（$2 \leq n, p, M, m \leq 4 \times 10^5$），分别表示投诉数量、电台数量、最大信号功率和互相干扰的电台对数。 接下来 $n$ 行，每行两个整数 $x_i$ 和 $y_i$（$1 \leq x_i < y_i \leq p$），表示第 $i$ 份投诉中提到的两个电台的编号。所有投诉互不相同。 接下来 $p$ 行，每行两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq M$），表示第 $i$ 个电台的信号功率要求。 接下来 $m$ 行，每行两个整数 $u_i$ 和 $v_i$（$1 \leq u_i < v_i \leq p$），表示互相干扰的电台对。所有这些对互不相同。

如果无法选择合适的信号功率和电台集合满足所有条件，输出 $-1$。 否则，第一行输出两个整数 $k$ 和 $f$，分别表示选中的电台数量和选择的信号功率。第二行输出 $k$ 个不同的整数，表示选中的电台编号（顺序任意）。如果有多组解，输出任意一组即可；不要求电台数量或信号功率的最小或最大值。

由 ChatGPT 4.1 翻译