Graph Coloring with Two Disjoint Paths

You are given a simple undirected graph with n vertices and m edges. The vertices are numbered from 1 to n. Your task is to assign each vertex a color, either black or white, such that:

• There is at least one black vertex.
• There is at least one white vertex.
• For every ordered pair of distinct vertices (u, v) with different colors, there exist at least two different simple paths from u to v.

A simple path is a path that does not visit any vertex more than once. Two simple paths are considered different if they have different lengths or there exists a positive integer i such that the i-th vertex in the two paths differ.

If such a coloring assignment does not exist, report that no solution exists.

Note: By Menger's theorem, the condition that any two vertices (of different colors) have at least two vertex-disjoint simple paths between them is equivalent to the graph being 2-vertex-connected (or 2-connected). Hence, a valid coloring exists if and only if the graph is connected and 2-connected (with n \ge 3).

inputFormat

The first line contains two integers n and m (1 \le n, m \le 10^5), the number of vertices and edges respectively.

Each of the next m lines contains two integers u and v (1 \le u, v \le n, u \neq v) representing an undirected edge between vertices u and v. There are no self-loops or multiple edges.

outputFormat

If a valid coloring exists, output a single line containing n tokens. The i-th token should be either Black or White denoting the color assigned to vertex i. If multiple answers exist, print any one of them.

If no valid coloring exists, output a single line with the string No solution.

sample

3 3
1 2
2 3
3 1

Black White White