← 返回题目列表

Codeforces · 1215/F

F. 广播电台

中文机器翻译题面 查看原题

除了有关照明的投诉外,伯敦市政厅近期也收到了大量有关无线电信号覆盖不足的投诉。 $$$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$$$ 和一组站来建立合同,以便:

- 所有投诉均得到满足(正式而言,对于 [1, n]$$$ 中的每个 $$$i \,城市与车站 $$$x_i$$$ 或与车站 $$$y_i$$$ 建立合同);
- 没有两个选定的电台相互干扰(正式地,对于 [1, m]$$$ 中的每个 $$$i \in,城市不与电台 $$$u_i$$$ 或与电台 $$$v_i$$$ 建立合同);
- 对于每个选定的电台,满足信号功率条件(正式来说,对于每个选定的电台 $$$i$$$ 满足条件 $$$l_i \le f \le r_i$$$)。

输入

第一行包含 $$$4$$$ 整数 $$$n$$$、$$$p$$$、$$$M$$$ 和 $$$m$$$ ($$$2 \le n, p, M, m \le 4 \cdot 10^5$$$) — 分别是投诉数量、广播电台数量、最大信号功率和干扰对数量。

接下来是 $$$n$$$ 行,描述投诉。每行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i < y_i \le p$$$) — 第 $$$i$$$ 投诉中提到的广播电台的索引)。所有投诉都是明确的。

接下来是 $$$p$$$ 行,描述广播电台。每行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le M$$$) — 如果城市与第 $$$i$$$ 站建立合同,则应满足信号功率的限制。

接下来是 $$$m$$$ 行,描述了干扰无线电台对。每行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i < v_i \le p$$$) — 干扰无线电台的索引。所有这些对都是不同的。

输出

如果无法选择信号功率和一组电台来满足所有条件,请打印$$$-1$$$。

否则在第一行打印两个整数 $$$k$$$ 和 $$$f$$$ — 分别是所选集合中的站数和所选信号功率。在第二行中打印 $$$k$$$ 从 $$$1$$$ 到 $$$p$$$ 的不同整数 - 与之建立合同的站的索引(以任何顺序)。如果有多个答案,打印其中一个;您不必最小化/最大化所选电台的数量,信号功率也是如此。

示例

输入 #1

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

输出 #1

2 3
1 3

输入 #2

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

输出 #2

-1