有两个长度为 $M$ 的整数数组 $A_1 \dots A_M ,B_1 \dots B_M$。保证 $1 \le A_i,B_i \le N$。现在有一个 $2N$ 个编号从 $1$ 到 $2N$ 的点的无向图，初始时第 $i$ 与 第 $i+N$ 号点相连，现在对于长为 $M$ 的 $0/1$ 串。

• 若 $M_i=0$ 则连接一条 $(A_i,B_{i}+N)$ 的无向边。
• 若 $M_i=1$ 则连接一条 $(A_{i}+N,B_i)$ 的无向边。

现在请你构造出一个长为 $M$ 的 $0/1$ 串，使得此无向图的桥最少。

数据范围

$1 \le N,M \le 2 \times 10^5$

$1 \le A_i,B_i \le N$

输入格式

第一行两个整数 $N,M$。

第二行 $M$ 个整数 $A_1 \dots A_M$。

第三行 $M$ 个整数 $B_1 \dots B_M$。