201433: [AtCoder]ARC143 D - Bridges

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $700$ points

Problem Statement

We have two sequences $A_1,\ldots, A_M$ and $B_1,\ldots,B_M$ consisting of intgers between $1$ and $N$ (inclusive).

For a string of length $M$ consisting of 0 and 1, consider the following undirected graph with $2N$ vertices and $(M+N)$ edges corresponding to that string.

  • If the $i$-th character of the string is 0, the $i$-th edge connects Vertex $A_i$ and Vertex $(B_i+N)$.
  • If the $i$-th character of the string is 1, the $i$-th edge connects Vertex $B_i$ and Vertex $(A_i+N)$.
  • The $(j+M)$-th edge connects Vertex $j$ and Vertex $(j+N)$.

Here, $i$ and $j$ are integers such that $1 \leq i \leq M$ and $1 \leq j \leq N$, and the vertices are numbered $1$ to $2N$.

Find one string of length $M$ consisting of 0 and 1 such that the corresponding undirected graph has the minimum number of bridges.

Notes on bridges A bridge is an edge of a graph whose removal increases the number of connected components.

Constraints

  • $1 \leq N \leq 2 \times 10^5$
  • $1 \leq M \leq 2 \times 10^5$
  • $1 \leq A_i, B_i \leq N$

Input

Input is given from Standard Input in the following format:

$N$ $M$
$A_1$ $A_2$ $\cdots$ $A_M$
$B_1$ $B_2$ $\cdots$ $B_M$

Output

Print one string that satisfies the requirement. If there are multiple such strings, you may print any of them.


Sample Input 1

2 2
1 1
2 2

Sample Output 1

01

The graph corresponding to 01 has no bridges.

In the graph corresponding to 00, the edge connecting Vertex $1$ and Vertex $3$ and the edge connecting Vertex $2$ and Vertex $4$ are bridges, so 00 does not satisfy the requirement.


Sample Input 2

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

Sample Output 2

0100010

Input

题意翻译

有两个长度为 $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$。

加入题单

上一题 下一题 算法标签: