32760번 - Nothing Everything 스페셜 저지

문제

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

• $i$번째 연산이 Nothing이라면, $i+1$번 정점을 추가한다. $i+1$번 정점에는 아무런 간선을 잇지 않는다.
• $i$번째 연산이 Everything이라면, $i+1$번 정점을 추가한다. $i+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임을, $j$번째 문자가 E라면 $j$번째 연산이 Everything임을 의미한다. 가능한 연산 과정이 여러 가지라면 그중 아무거나 하나를 출력한다.

만약 두 연산으로 주어진 그래프 $G$를 만들 수 없다면 -1을 대신 출력한다.

제한

• 2ドル \le N \le 100,000円$
• 0ドル \displaystyle \le M \le \min \left( \frac{N(N-1)}{2}, 100,000円 \right)$
• 1ドル \le a_i, b_i \le N$
• $a_i \neq b_i$

힌트