This is a communication problem.

An exam is taking place.

The content of this exam is quite simple—given an undirected graph $ G = (V, E) $ with $ N $ vertices and $ M $ edges, where the $ i $-th edge ($ 0 \leq i < M $) connects the two vertices $ (U_i, V_i) $ ($ 0 \leq U_i, V_i < N $). It is guaranteed that the graph contains no multiple edges or self-loops. The task is to assign each vertex a color from the set {0, 1, 2, 3, 4, 5, 6, 7} such that the two endpoints of any edge have different colors.

Alice, using her magical powers, quickly finds a valid coloring solution and passes the exam.

Bob also wants to find such a solution, so he decides to secretly communicate with Alice. Alice can send Bob a binary string $ X $ of length $ L $ to give him some hints. Subsequently, Bob needs to construct any valid 8-coloring solution.

Implementation Details

This is a communication problem, and the problem only supports the C++ language. You need to submit two programs.

Alice

The first program you need to submit is Alice, which describes Alice's strategy.

You need to implement the following function:

std::vector <int> Alice(int N, int M, std::vector <int> U, std::vector <int> V, std::vector <int> C);

• N represents the number of vertices $ N $ in the graph $ G $.
• M represents the number of edges $ M $ in the graph $ G $.
• U, V are arrays of length $ M-1 $ that describe the edges of the graph.
• C is an array of length $ N $, where $ C_0, C_1, \cdots, C_{N-1} $ ($ 0 \leq C_i < 8 $) describes the colors assigned by Alice in the 8-coloring.
• This function needs to return an array $ X $:
  • Let $ L = |X| $.
  • You need to ensure $ 0 \leq L < 6 \times 10^5 $.
  • You need to ensure that for any $ 0 \leq i < L $, $ X_i $ is either 0 or 1.
• In each test case, this function will be called exactly once.

Bob

The second program you need to submit is Bob, which describes Bob's strategy.

You need to implement the following function:

std::vector <int> Bob(int N, int M, std::vector <int> U, std::vector <int> V, std::vector <int> X);

• N represents the number of vertices $ N $ in the graph $ G $.
• M represents the number of edges $ M $ in the graph $ G $.
• U, V are arrays of length $ M-1 $ that describe the edges of the graph.
• X is the array returned by Alice.
• This function needs to return an array $ C' $:
  • You need to ensure that $ |C'| = N $.
  • You need to ensure that for any $ 0 \leq i < N $, $ 0 \leq C'_i < 8 $.
  • You need to ensure that for any $ 0 \leq i < M $, $ C'_{U_i} \neq C'_{V_i} $.
• In each test case, this function will be called exactly once.

Sample Interaction Library

The provided files include a sample interaction library grader.cpp. You can compile the executable answer using the following command:

g++ grader.cpp Alice.cpp Bob.cpp -o answer -O2

The executable will read the following input format from standard input (stdin):

• The first line of input contains two integers $ N $ and $ M $.
• The next $ M $ lines each contain two integers $ U_i $ and $ V_i $.
• The next line contains $ N $ integers $ C_0, C_1, \cdots, C_{N-1} $.

If your program runs correctly, the executable will output the following format:

• One line containing $ N $ integers $ C'_0, C'_1, \cdots, C'_{N-1} $.

Please note that the interaction library used in the final evaluation will differ from this sample interaction library. Contestants should not rely on the specific implementation of this sample library.

Sample Data

Sample Input

10 14
2 8
3 2
2 4
6 5
3 5
4 8
8 6
7 6
2 7
0 6
4 7
1 4
3 0
4 3
1 5 2 0 4 5 2 1 7 2

Sample Output

0 0 0 1 2 0 1 3 3 0

Subtasks

For all data, $ 1 \leq N \leq 2 \times 10^5 $, $ 0 \leq M \leq 5 \times 10^5 $.

In each test point, if you exceed the time limit (2.0 seconds), the space limit (256 MiB), encounter a runtime error, or the final constructed solution is invalid, your score will be 0.

• Please note: The time limit means that the maximum runtime of both of your programs combined cannot exceed 2.0 seconds. The space limit means that the maximum space used by both of your programs combined cannot exceed 256 MiB.
• In any valid (scorable) interaction, the interaction library will use no more than 12 MiB of memory and no more than 0.05 seconds between two calls. Therefore, you actually have at least 1.95 seconds and at least 244 MiB of space available.

Otherwise, your score depends on the value of $ L = |X| $, the time $ t $ (in seconds) used by your program, and the memory $ m $ (in MB) used by your program:

• The parameter $ S $ depends on the value of $ L $:
  • If $ L \leq 2.5 \times 10^5 $, then $ S = 100 $.
  • If $ 2.5 \times 10^5 < L \leq 6 \times 10^5 $, then $ S = 2 + 95 \times \left(\frac{600\,000 - L}{350\,000}\right)^2 $.
  • Otherwise, $ S = 0 $.
• The parameter $ K_1 $ depends on the value of $ t $:
  • If $ t \leq 0.5 $, then $ K_1 = 1 $.
  • If $ 0.5 < t \leq 2.0 $, then $ K_1 = (1-\frac{1}{2}t) + 0.05 $.
  • Otherwise, $ K_1 = 0 $.
• The parameter $ K_2 $ depends on the value of $ m $:
  • If $ m \leq 32 $, then $ K_2 = 1 $.
  • If $ 32 < m \leq 256 $, then $ K_2 = (1-\frac{1}{256}m) $.
  • Otherwise, $ K_2 = 0 $.
• Finally, your score is $ K_1 \times K_2 \times S $.

In summary, to achieve a perfect score, the binary string you transmit should be no longer than $ 2.5 \times 10^5 $ bits, and the time used by your programs (including the interaction library) should not exceed 0.5 seconds, with memory usage not exceeding 32 MiB (including the interaction library, which means your programs should use no more than 20 MiB of space).