H. Cual es Tacafroto
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A group of friends is trapped inside an abandoned building that has been converted into a giant escape room. The building's layout is modeled as a simple, connected, undirected graph where each node represents a room and each edge represents a corridor connecting two rooms.

One of the friends —Mr. Tacafroto— managed to reach the control room. In this room, Tacafroto has full access to the building's lighting system and blueprints. Each corridor is equipped with its own light that can shine in a fixed color. However, the building is initially in complete darkness: all corridor lights are turned off. Tacafroto can activate the lights, but with one important constraint: at any given moment, he may turn on the lights of only one chosen color.

Before issuing any instructions, Tacafroto is allowed to set up the building's corridors as follows:

Assignment of Colors: Each corridor (i.e., every existing undirected edge) is assigned a color from the set $$$\{ 1,2,3 \}$$$. That is, every corridor has its dedicated light of a specific color.

Optional Passage: He may also build at most one new one-way passage (a directed edge) connecting two rooms that are not already connected. This new passage is assigned a color (from 1 to 3) just like the other corridors.

The remaining friends are stuck in different rooms. Tacafroto does not know exactly how many friends there are, nor in which rooms they are located. To gather them, Tacafroto can issue a sequence of instructions. In each instruction he selects a color $$$c \in \{ 1,2,3 \}$$$ and performs the following steps:

All corridor lights are turned off first.

Then, the lights for all corridors whose assigned color is $$$c$$$ (including the light of the extra one-way passage, if one was built and have color $$$c$$$) are turned on.

Immediately after, every friend (regardless of their room) makes a move:

If there is at least one corridor from their current room whose light is on (i.e., whose assigned color is c), the friend must choose one such corridor and move to the adjacent room.

If there are multiple illuminated options, the friend may pick any of them arbitrarily. Tacafroto does not control these choices and has no knowledge of the friends movements.

If no corridor from their room is lit, the friend remains in place.

The goal is to design the initial color assignments (and optionally, add the directed passage) along with a sequence of at most 205 instructions —each instruction simply a color— to guarantee that, regardless of how many friends there are or where they start, all friends eventually meet in the same room.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ — the number of rooms and the number of corridors in the building, respectively. $$$ 2 \leq n \leq 200,\quad 1 \leq m \leq \frac{n(n-1)}{2} $$$

Each of the next $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ $$$(1 \le u, v \le n,\ u \ne v)$$$, indicating that there is a corridor connecting room $$$u$$$ and room $$$v$$$.

It is guaranteed that:

  • The graph is connected.
  • There are no multiple corridors between the same pair of rooms.
  • There are no loops, i.e., $$$u \ne v$$$.
Output

If it is impossible to guarantee that all friends will meet in the same room within at most 205 instructions, print "NO" in a single line (without quotes).

Otherwise, output the following:

  • The first line should contain the string "SI" (without quotes).

  • The second line should contain three integers $$$u$$$, $$$v$$$, and $$$c$$$ $$$(1 \le u,v \le n,\ 1 \le c \le 3)$$$, representing a new directed edge from room $$$u$$$ to room $$$v$$$ with color $$$c$$$. If you choose not to add a new edge, print "-1 -1 -1" (without quotes).

  • The next $$$m$$$ lines should each contain an integer $$$c_i \in \{1,2,3\}$$$, representing the color assigned to the $$$i$$$-th undirected corridor (in the same order as given in the input).

  • The last line should contain a string of length at most 205, consisting only of the digits 1, 2, and 3. This string represents the sequence of instructions that Tacafroto gives to the friends. Each character corresponds to one move: the number indicates the color whose lights are turned on in that step.

Your output must guarantee that, no matter how many friends there are and in which rooms they start, all of them will eventually meet in the same room after following the given sequence of instructions.

Example
Input
3 2
1 2
1 3
Output
SI
2 3 1
2
3
121