Nothing Everything

정점이 $N$개이고 간선이 $M$개인 무방향 그래프 $G$가 주어진다. 처음에 그래프에는 $1$번 정점만 있다. 다음 두 연산을 $N - 1$번 사용해 그래프 $G$를 만들 수 있는지 판별하고, 만들 수 있다면 연산 순서를 출력하라.

• $i$번째 연산이 Nothing이라면, $i+1$번 정점을 추가한다. 이때 $i+1$번 정점에는 간선을 잇지 않는다.
• $i$번째 연산이 Everything이라면, $i+1$번 정점을 추가한다. 이때 $i+1$번 정점을 $1$번부터 $i$번까지 모든 정점과 간선으로 잇는다.

첫 번째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다.

두 번째 줄부터 $M$개의 줄에 걸쳐 간선 정보가 주어진다. $i$번째 줄에는 $a_i$와 $b_i$가 공백으로 구분되어 주어지며, 이는 그래프 $G$에 $a_i$번 정점과 $b_i$번 정점을 잇는 간선이 있다는 뜻이다. 그래프 $G$에 중복된 간선은 없다.

두 연산으로 그래프 $G$를 만들 수 있다면 첫 번째 줄에 길이가 $N - 1$이고 N과 E로만 이루어진 문자열을 출력한다. $j$번째 문자가 N이면 $j$번째 연산은 Nothing이고, E이면 Everything이다. 가능한 연산 순서가 여러 개라면 그중 아무거나 하나를 출력한다.

만들 수 없다면 -1을 출력한다.

• $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$