D. Please solve this in O(N^3)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an undirected graph with $$$N$$$ nodes and $$$M$$$ edges. Each node is assigned a bitmask $$$A$$$ (where $$$1 \leq A \leq 2^{30} - 1$$$). A node is said to 'contain' color $$$c$$$ (with $$$0 \leq c \leq 29$$$) if the bit in the $$$2^c$$$ place in the binary representation of $$$A$$$ is $$$1$$$. This expression using bitwise operators would evaluate to true if and only if $$$A$$$ contains the color $$$c$$$.

$$$$$$ (A \ \& \ (1 \ll c)) == (1 \ll c) $$$$$$

A path between two nodes $$$i$$$ and $$$j$$$ is considered valid if there exists at least one color $$$c$$$ such that every node along the path (including $$$i$$$ and $$$j$$$) contains color $$$c$$$.

Your task is to determine, for every node $$$i$$$, which nodes $$$j$$$ are reachable from $$$i$$$ via some valid path. Output an $$$N \times N$$$ matrix of characters, where the $$$j$$$th character in the $$$i$$$th row is '1' if there exists at least one valid path from node $$$i$$$ to node $$$j$$$, and '0' otherwise.

Input

The first line contains two integers $$$N (1 \leq N \leq 500)$$$ and $$$M(0 \leq M \leq \frac{N \times (N - 1)}{2})$$$, the number of nodes and the number of edges.

The second line contains $$$N$$$ integers, where the $$$i$$$th integer is the bitmask $$$A_i (1 \leq A_i \leq 2^{30} - 1)$$$ for node $$$i$$$.

The following $$$M$$$ lines each contain two integers $$$u$$$ and $$$v$$$ representing an undirected edge between nodes $$$u$$$ and $$$v$$$. Nodes are numbered from $$$1$$$ to $$$N$$$. It is guaranteed there are no duplicate edges or self loops.

—

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Test $$$1$$$ satisfies $$$M = 0$$$.

Test $$$2$$$ satisfies $$$M = \frac{N \times (N - 1)}{2}$$$.

Tests $$$3-6$$$ satisfy $$$A_i = 1$$$.

Tests $$$7-20$$$ satisfy no additional constraints.

Output

Output $$$N$$$ lines. The $$$i$$$th line should be a string of $$$N$$$ characters. The $$$j$$$th character in this string should be '1' if there exists a valid path from node $$$i$$$ to node $$$j$$$, and '0' otherwise.

—

Problem Idea: Alex_C

Problem Preparation: nyctivoe

Occurrences: Novice D

Examples
Input
5 5
1 2 3 4 5
1 3
2 3
3 5
5 4
2 4
Output
10101
01100
11101
00011
10111
Input
10 13
3 5 2 7 1 8 6 9 10 4
1 2
1 3
2 4
3 4
4 5
1 4
2 3
6 8
8 9
9 7
7 10
8 10
4 7
Output
1111101010
1101101001
1011001010
1111101011
1101100000
0000010110
1111001011
0000010110
1011011110
0101001001