Nothing Everything

Time limit1sMemory limit1024 MB

Summary

Decide whether a graph can be built by adding each vertex either isolated or joined to all earlier vertices, and output the operations if it can.

Level: Medium5 of 10
Topics: Graph, Greedy, Implementation
Solved: No attempts yet

Problem

A undirected graph $G$ has $N$ vertices and $M$ edges. At the start, the graph contains only vertex $1$ . Determine whether $G$ can be built by performing the following two operations $N - 1$ times, and if it can, print the sequence of operations in order.

If the $i$ -th operation is Nothing, add vertex $i+1$ with no edges connecting it to any other vertex.
If the $i$ -th operation is Everything, add vertex $i+1$ and connect it with an edge to every vertex from $1$ to $i$ .

Input

The first line contains $N$ and $M$ , separated by a space.

Each of the next $M$ lines contains $a_i$ and $b_i$ , separated by a space. This means that graph $G$ has an edge between vertex $a_i$ and vertex $b_i$ . Graph $G$ has no duplicate edges.

Output

If $G$ can be built with the two operations, print on the first line a string of length $N - 1$ consisting only of N and E. The $j$ -th character is N if the $j$ -th operation is Nothing, and E if it is Everything. If there are several valid sequences, print any one of them.

If $G$ cannot be built, print -1.

Constraints

$2 \le N \le 100\,000$
$0 \le M \le \min \left( \frac{N(N-1)}{2}, 100\,000 \right)$
$1 \le a_i, b_i \le N$
$a_i \ne b_i$

Examples3

Example 1
Input
```
2 0
```
Expected output
```
N
```
Example 2
Input
```
3 3
2 1
3 2
1 3
```
Expected output
```
EE
```
Example 3
Input
```
4 2
1 2
3 4
```
Expected output
```
-1
```