I. Distance

除了关于照明的投诉外，最近贝托恩市市政厅还收到了大量关于无线电信号覆盖不足的投诉。市长收到了 n 封投诉，它们都惊人地相似：在第 i 封投诉中，一位无线电爱好者提到，两家电台 x_i 和 y_i 的信号无法覆盖城市的一些区域，并要求至少其中一家电台的信号能够覆盖整个城市。 当然，贝托恩市长目前正在努力满足这些投诉。一座新的无线电塔已在贝托恩安装，它可以以 1 到 M 之间的任意整数功率发射信号（记信号功率为 f）。市长决定选择一组电台，并与每个被选中的电台签订合同。要与第 i 家电台签订合同，必须满足以下条件： 所有这些信息已经足以让市长意识到选择电台非常困难。但经过与专家咨询后，他了解到某些电台的信号可能会相互干扰：存在 m 对电台 (u_i, v_i) 使用相同的信号频率，对于每一对这样的电台，不可能同时与两家签订合同。*如果电台 x 和 y 使用相同的频率，且 y 和 z 使用相同的频率，并不意味着 x 和 z 使用相同的频率*。 市长发现分析这种情况非常困难，因此聘请了你来帮助他。你需要选择一个信号功率 f 和一组电台来签订合同，使得： 第一行包含 4 个整数 n, p, M 和 m（2 \leq n, p, M, m \leq 4 \cdot 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 个从 1 到 p 的互不相同的整数 —— 要签订合同的电台编号（顺序任意）。如果有多个答案，输出任意一个即可；你无需最小化或最大化所选电台数量，信号功率同理。 ## Input 第一行包含 4 个整数 n, p, M 和 m（2 \leq n, p, M, m \leq 4 \cdot 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）——干扰电台的编号。*所有这些对互不相同*。 ## Output 如果无法选择信号功率和一组电台以满足所有条件，请输出 -1。否则，第一行输出两个整数 k 和 f —— 所选电台的数量和选定的信号功率。第二行输出 k 个从 1 到 p 的互不相同的整数 —— 要签订合同的电台编号（顺序任意）。如果有多个答案，输出任意一个即可；你无需最小化或最大化所选电台数量，信号功率同理。 [samples]

Let $ A, B, R \in \mathbb{Z}^+ $ with $ 1 \leq A \leq B \leq 10^7 $ and $ R \geq 1 $. Let $ X \in \mathbb{R} $ denote the radius of the red circle. The configuration requires: - One red circle of radius $ X $. - An arbitrary number $ n \geq 3 $ of yellow circles, each of radius $ R $, arranged in a closed chain such that: - Each yellow circle is externally tangent to two adjacent yellow circles. - Each yellow circle is externally tangent to the red circle. - No circle lies inside another. This forms a regular $ n $-gon of yellow circles centered around the red circle. The centers of the yellow circles lie on a circle of radius $ X + R $ centered at the red circle’s center. The distance between centers of two adjacent yellow circles is $ 2R $. By the law of cosines in the triangle formed by two adjacent yellow centers and the red center: $$ (2R)^2 = 2(X + R)^2 (1 - \cos \theta), \quad \text{where } \theta = \frac{2\pi}{n} $$ Solving: $$ 4R^2 = 2(X + R)^2 \left(1 - \cos \frac{2\pi}{n}\right) $$ $$ (X + R)^2 = \frac{2R^2}{1 - \cos \frac{2\pi}{n}} $$ $$ X = \sqrt{ \frac{2R^2}{1 - \cos \frac{2\pi}{n}} } - R $$ Using identity $ 1 - \cos \theta = 2 \sin^2(\theta/2) $: $$ X = \frac{R}{\sin(\pi/n)} - R = R \left( \frac{1}{\sin(\pi/n)} - 1 \right) $$ Let $ f(n) = R \left( \frac{1}{\sin(\pi/n)} - 1 \right) $ for integers $ n \geq 3 $. We seek the number of distinct real values $ X = f(n) \in [A, B] $ for $ n \in \mathbb{Z}, n \geq 3 $. Define: $$ \mathcal{X} = \left\{ R \left( \frac{1}{\sin(\pi/n)} - 1 \right) \,\middle|\, n \in \mathbb{Z}, n \geq 3, \, A \leq R \left( \frac{1}{\sin(\pi/n)} - 1 \right) \leq B \right\} $$ **Objective:** Compute $ |\mathcal{X}| $, the number of distinct $ X \in [A, B] $ achievable via integer $ n \geq 3 $.