心理暗示

猜猜看吧。

题目描述

卡芙卡在练习言灵，这时候你刚好路过，于是她把你拽了过来。她使用言灵让你做如下工作：

现在有一个有 $n$ 个点和 $m$ 条边的无向图，不保证没有重边，不保证图联通。对于每一个点卡芙卡会给出一个整数 $a_i$ 表示其颜色，保证 $1\leq a_i\leq 4$，保证每一条边的两个端点颜色不同。

现在卡芙卡又给了你三种颜色，用 $1,2,3$ 表示，她想让你给出一种方案，使得所有三元环中三边颜色互不相同。

方案数可能有很多，你只需要给出其中的一种即可。

输入格式

第一行输入两个个正整数 $n,m$，分别表示点数和边数。

第二行输入 $n$ 个正整数，用空格间隔，依次表示每个点的颜色 $a_i$，保证 $1\leq a_i\leq 4$。

接下来的 $m$ 行，每行两个正整数 $x,y$，表示一条边。

输出格式

输出 $m$ 行，按边的输入顺序给出每条边的颜色。

样例 #1

样例输入 #1

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

样例输出 #1

1
1
3
3
2
3
3
2

样例 #2

样例输入 #2

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

样例输出 #2

3 
1 
2 
3 
1 
2

样例补充说明

本题开启 Special Judge(by 赵翰文，基于 SA 算法实现) ，输出任意一种合法方案即可。 如样例 #2，输出还可以是

1 
2 
3 
1 
2 
3

数据范围

本题采用捆绑测试。

• Subtask 1 ( $20pts$ )：$n=10,1\leq m\leq 50$。
• Subtask 2 ( $30pts$ )：$n=100,1\leq m\leq 1000$。
• Subtask 3 ( $50pts$ )：$n=3000,1\leq m\leq 5\times 10^5$。

不保证图无重边，不保证图连通。

建议解流，快读也会被卡掉。