P9925 [POI 2023/2024 R1] Zapobiegliwy student

译自 [XXXI Olimpiada Informatyczna - I etap](https://sio2.mimuw.edu.pl/c/oi31-1/dashboard/) [Zapobiegliwy student](https://sio2.mimuw.edu.pl/c/oi31-1/p/zap/)。

考虑如下的一个简单问题： > 你有 $n$ 个线段在数轴上，你要选出尽量多的线段，使它们两两不交。 我知道你一定会做，但你需要解决这个： 你有 $n$ 个线段在数轴上，你要选出尽量多的线段对 $(u_i,v_i)_{i=1}^k$，即最大化 $k$。 满足 $k+1$ 个要求： - $u_1,u_2,\cdots,u_k$ 两两不交。 - $v_1,u_2,u_3,\cdots,u_k$ 两两不交。 - $u_1,v_2,u_3,u_4,\cdots,u_k$ 两两不交。 - $\cdots$ - $u_1,u_2,\cdots,u_{k-1},v_k$ 两两不交。 其中 $\forall i$，$u_i$ 与 $v_i$ 不能相同。

第一行一个正整数 $n(n\geq2)$。 接下来 $n$ 行每行两个正整数 $a_i,b_i(1\leq a_i

第一行一个正整数 $k$。 接下来 $k$ 行，每行两个正整数 $u_i,v_i$，表示一对线段的编号。

如果你的第一行正确但是方案不对（可以不输出方案，此时不要有换行），你能得到 $50\%$ 的分数。 如果你的方案合法并且第一行和答案相差不超过 $1$，你能得到 $15\%$ 的分数。 | 子任务编号 | 限制 | 分值 | | :----------: | :----------: | :----------: | | 1 | $n\leq3000$ | 40 | | 2 | $n\leq500000$ | 60 |