一维数轴上有 n 个初始不重叠的动点,它们初始有某个固定的朝向,但可以以任意的非零速率运动。
如果某两个动点 u v 在运动过程中保证一定会相遇,那么这两个点的关系就称为注定相关(destined)。
如果某两个动点 u v 在运动过程中保证一定不会相遇,那么这两个点的关系就称为不相关(irrelevant)。
现在给定了 m 对关系,要求给出一种方案(即所有动点的初始位置 xi、朝向 orii∈{L,R})满足这些关系,或判断无解。
2≤n≤2⋅105, 1≤m≤min(2⋅105,2n(n−1))
一维数轴上有 $n$ 个初始不重叠的动点,它们初始有某个**固定**的朝向,但可以以**任意**的非零速率运动。
如果某两个动点 $u$ $v$ 在运动过程中保证一定会相遇,那么这两个点的关系就称为**注定相关(destined)**。
如果某两个动点 $u$ $v$ 在运动过程中保证一定不会相遇,那么这两个点的关系就称为**不相关(irrelevant)**。
现在给定了 $m$ 对关系,要求给出一种方案(即所有动点的初始位置 $x_i$、朝向 $ori_i\in\{L,R\}$)满足这些关系,或判断无解。
$2 \leq n\leq 2\cdot 10^5,\ 1\leq m \leq \min(2\cdot 10^5,\frac{n(n-1)}{2})$