CF1215F.Radio Stations

In addition to complaints about lighting, a lot of complaints about insufficient radio signal covering has been received by Bertown city hall recently. $n$ complaints were sent to the mayor, all of which are suspiciosly similar to each other: in the $i$-th complaint, one of the radio fans has mentioned that the signals of two radio stations $x_i$ and $y_i$ are not covering some parts of the city, and demanded that the signal of at least one of these stations can be received in the whole city.

Of cousre, the mayor of Bertown is currently working to satisfy these complaints. A new radio tower has been installed in Bertown, it can transmit a signal with any integer power from $1$ to $M$ (let's denote the signal power as $f$). The mayor has decided that he will choose a set of radio stations and establish a contract with every chosen station. To establish a contract with the $i$-th station, the following conditions should be met:

• the signal power $f$ should be not less than $l_i$, otherwise the signal of the $i$-th station won't cover the whole city;
• the signal power $f$ should be not greater than $r_i$, otherwise the signal will be received by the residents of other towns which haven't established a contract with the $i$-th station.

All this information was already enough for the mayor to realise that choosing the stations is hard. But after consulting with specialists, he learned that some stations the signals of some stations may interfere with each other: there are $m$ pairs of stations ($u_i$, $v_i$) that use the same signal frequencies, and for each such pair it is impossible to establish contracts with both stations. If stations $x$ and $y$ use the same frequencies, and $y$ and $z$ use the same frequencies, it does not imply that $x$ and $z$ use the same frequencies.

The mayor finds it really hard to analyze this situation, so he hired you to help him. You have to choose signal power $f$ and a set of stations to establish contracts with such that:

• all complaints are satisfied (formally, for every $i \in [1, n]$ the city establishes a contract either with station $x_i$, or with station $y_i$);
• no two chosen stations interfere with each other (formally, for every $i \in [1, m]$ the city does not establish a contract either with station $u_i$, or with station $v_i$);
• for each chosen station, the conditions on signal power are met (formally, for each chosen station $i$ the condition $l_i \le f \le r_i$ is met).

除了关于照明的投诉外，伯特城市政厅最近还收到了大量关于无线电信号覆盖不足的投诉。共有 $n$ 条投诉提交给了市长，这些投诉彼此之间 suspiciously 相似：在第 $i$ 条投诉中，某位无线电爱好者指出，两个广播电台 $x_i$ 和 $y_i$ 的信号未能覆盖城市的某些区域，并要求至少其中一个电台的信号能在全城范围内被接收到。

当然，伯特城市长正努力满足这些投诉。一座新的无线电发射塔已在伯特城建成，它可发射任意整数功率 $f$ 的信号，其中 $f$ 的取值范围为 $1$ 到 $M$（我们记该信号功率为 $f$）。市长决定选择一组广播电台，并与每个被选中的电台签订合同。要与第 $i$ 个电台签订合同，必须满足以下条件：

• 信号功率 $f$ 不得小于 $l_i$，否则第 $i$ 个电台的信号将无法覆盖全城；
• 信号功率 $f$ 不得大于 $r_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$ 签订合同）；
• 对每个被选中的电台 $i$，其关于信号功率的约束均被满足（形式化地，对每个被选中的电台 $i$，均有 $l_i \le f \le r_i$）。

The first line contains $4$ integers $n$, $p$, $M$ and $m$ ($2 \le n, p, M, m \le 4 \cdot 10^5$) — the number of complaints, the number of radio stations, maximum signal power and the number of interfering pairs, respectively.

Then $n$ lines follow, which describe the complains. Each line contains two integers $x_i$ and $y_i$ ($1 \le x_i \lt y_i \le p$) — the indices of the radio stations mentioned in the $i$-th complaint). All complaints are distinct.

Then $p$ lines follow, which describe the radio stations. Each line contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le M$) — the constrains on signal power that should be satisfied if the city establishes a contract with the $i$-th station.

Then $m$ lines follow, which describe the pairs of interfering radio stations. Each line contains two integers $u_i$ and $v_i$ ($1 \le u_i \lt v_i \le p$) — the indices of interfering radio stations. All these pairs are distinct.

第一行包含 $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 \lt 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 \lt v_i \le p$），表示相互干扰的广播电台的编号。所有此类电台对互不相同。

If it is impossible to choose signal power and a set of stations to meet all conditions, print $-1$.

Otherwise print two integers $k$ and $f$ in the first line — the number of stations in the chosen set and the chosen signal power, respectively. In the second line print $k$ distinct integers from $1$ to $p$ — the indices of stations to establish contracts with (in any order). If there are multiple answers, print any of them; you don't have to minimize/maximize the number of chosen stations, and the same applies to signal power.

如果无法选择信号功率和一组基站来满足所有条件，则输出 $-1$。

否则，在第一行输出两个整数 $k$ 和 $f$ —— 分别表示所选基站的数量和所选的信号功率。在第二行输出 $k$ 个互不相同的、取值范围为 $1$ 到 $p$ 的整数 —— 表示需签订合同的基站编号（顺序任意）。若存在多个可行解，输出任意一个即可；无需最小化或最大化所选基站的数量，对信号功率亦同理。