[R6C]分班 - 代码源竞赛平台

时空限制

2S/512M

题目描述

有 $n$ 个学生，编号 $1\sim n$，其中 $i$ 号学生的团结度为 $a_i$。现在将这 $n$ 名学生分到1、2两班，每个班的总团结度为当前分到这个班的学生的团结度之和。

但是学生之间存在 $m$ 条矛盾关系，第 $i$ 条矛盾关系说明 $u_i$ 号学生和 $v_i$ 号学生之间相互有矛盾。

将 $n$ 个学生按编号从小到大顺序分，轮到某一学生时：

• 如果两个班都已经分到与他有矛盾的学生，那么他会退出本次分班；
• 如果其中一个班已经分到与他有矛盾的学生，那么他会被分到另一个班；
• 如果两个班都还没分到与他有矛盾的学生，他会被分到总团结度更低的那个班，如果两个班当前总团结度一样则分到1班。

格式

输入格式

第一行包含一个整数 $n$，表示学生数量。

第二行包含 $n$ 个整数 $a_i$，分别表示每个学生的团结度。

第三行包含一个整数 $m$ ，表示矛盾关系的数量。

接下来 $m$ 行每行包含两个整数 $u_i$ 和 $v_i$，表示 $u_i$ 号学生和 $v_i$ 号学生之间相互有矛盾。

输出格式

输出 $n$ 行每行一个整数，第 $i$ 行的整数表示 $i$ 号学生的分班结果。如果 $i$ 号学生退出本次分班输出 $-1$，否则输出 $1$ 或 $2$ 表示他被分到哪个班。

样例

样例输入 #1

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

样例输出 #1

1
2
-1
2
2

数据规模

对于 $50\%$ 的数据，$n\leq 1000$。

对于 $100\%$ 的数据，$1\leq n\leq 10^5$，$1\leq a_i \leq 10^9$，$0\leq m\leq \min(\frac{n\times (n-1)}{2},2\times 10^6)$，$1\leq u_i,v_i\leq n$。数据保证 $u_i\neq v_i$。