This is a communication problem.

An exam is taking place.

The content of this exam is very simple: given an undirected graph $G=(V, E)$ with $N$ vertices and $M$ edges, the $i$-th edge ($0 \leq i < M$) connects the two endpoints $(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 of the exam is to assign a color $C_i \in \{0, \dots, 7\}$ to each vertex such that the endpoints of any edge have different colors.

Alice has quickly obtained a valid coloring scheme through her divine power and passed the exam.

Bob also wants to obtain such a scheme, so he decides to secretly communicate with Alice. Alice can send a binary string $X$ of length $L$ to Bob to provide some information. Subsequently, Bob needs to construct any valid 8-coloring scheme.

Formal Problem Statement

Two programs each have an undirected graph. The first program, Alice, possesses a valid 8-coloring scheme and can send information to the second program so that the second program can construct any valid 8-coloring scheme.

Implementation Details

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

Alice

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

You must include the header file Alice.h and implement the following function:

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

• In each test case, this function will be called exactly once.
• N represents the number of vertices $N$ in graph $G$.
• M represents the number of edges $M$ in graph $G$.
• U and V are arrays of length $M$, describing the edges in the graph.
• C is an array of length $N$, $C_0, C_1, \dots, C_{N-1}$ ($0 \leq C_i < 8$), describing the color of the $i$-th vertex in the 8-coloring constructed by Alice.
• This function needs to return an array $X$:
  • Let $L = |X|$.
  • You must ensure $0 \leq L < 6 \times 10^5$.
  • You must ensure that for any $0 \leq i < L$, $X_i \in \{0, 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 must include the header file Bob.h and implement the following function:

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

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

Sample Interactor

The provided files contain a sample interactor grader.cpp. You can compile it into an executable named answer using the following command:

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

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

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

If your program terminates normally, the executable will output the following to standard output:

• A single line containing $N$ integers $C'_0, C'_1, \dots, C'_{N-1}$.

During final evaluation, the programs Alice and Bob will be compiled separately and run in two different processes. The time limit (1.0 second) and memory limit (256 MiB) refer to the maximum time and memory that each process can use. Exceeding these limits in either process will result in a corresponding error. It is guaranteed that during final evaluation, the interactor for each of the three programs will use no more than 0.1 seconds of time and 16 MiB of memory, meaning the contestant has at least 0.9 seconds of time and 240 MiB of memory available.

Examples

Input 1

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

Output 1

0 0 0 1 2 0 1 3 3 0

Subtasks

Please note that the total score for this problem is 75 points.

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

In each test case, if you exceed the time limit (1.0 second), exceed the memory limit (256 MiB), encounter a runtime error, or the final constructed scheme is invalid, your score will be 0.

• Note: The time limit refers to the maximum running time of your two programs, which cannot exceed 1.0 second. The memory limit refers to the maximum memory used by your two programs, which cannot exceed 256 MiB.
• In any valid (score-earning) interaction, the interactor will use no more than 12 MiB of memory and 0.05 seconds of time across both calls.

Otherwise, your score depends on the value of $L = |X|$:

• The parameter $S$ is related to the value of $L$:
  • If $L \leq 2.5 \times 10^5$, then $S = 7$.
  • If $2.5 \times 10^5 < L \leq 6 \times 10^5$, then $S = \left\lfloor 7 \times \left(\frac{600\,000 - L}{350\,000}\right)^2 \right\rfloor$.
  • Otherwise, $S = 0$.
• Your final score is $S$.

That is, to obtain the full score, you can transmit a binary string of length at most $2.5 \times 10^5$.