Hexagonal Grid Coloring

You are given a hexagonal grid represented as an undirected graph with n cells (vertices) and m edges. Each edge connects two adjacent hexagons. The task is to determine whether it is possible to color the hexagons using two colors: Red (R) and Blue (B) such that no two adjacent hexagons share the same color.

If a valid coloring exists, output Possible on the first line and on the second line output a string of length n representing the color configuration. The color of the i^th hexagon is determined by the i^th character in the string where 'R' denotes Red and 'B' denotes Blue. If there are multiple solutions, any valid configuration is acceptable. Otherwise, output Impossible.

This problem is equivalent to checking if the graph is bipartite. Formally, a graph is bipartite if it is possible to assign one of two colors to each vertex such that for every edge \( (u,v) \),

[ \text{color}(u) \neq \text{color}(v). ]

inputFormat

The input is read from standard input and has the following format:

<n> <m>
<u1> <v1>
<u2> <v2>
... (m lines total)

Here, n is the number of hexagons (vertices) and m is the number of edges. Each of the following m lines contains two integers \( u \) and \( v \) (1-indexed) indicating that there is an edge between hexagon \( u \) and hexagon \( v \).

outputFormat

Output to standard output:

• If a valid 2-coloring exists, print Possible on the first line and on the second line print a string of length n where each character is either 'R' or 'B'.
• If no valid coloring exists, print Impossible.

## sample

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

Possible
RBBRRB

</p>