왕국

바이트리아에는 도시가 $n$개 있고, 도시를 잇는 양방향 도로가 짝수 개 있다. 도로망은 왕국의 아무 두 도시 사이든 오갈 수 있게 이어져 있다.

왕 바이트는 짝수를 좋아한다. 어떤 도시에서 나가는 도로가 홀수 개라는 사실을 알고는 곧바로 도로망을 늘리라고 명했다.

참모는 왕국 재정을 잘 안다. 그 공사를 강행하면 백성이 고대하는 동계 올림픽을 열 수 없다. 그래서 바이트리아에 짝수인 성질이 이미 충분하다고 왕을 설득하고, 공사는 내년으로 미뤄 달라고 청할 생각이다.

먼저, 나가는 도로가 홀수 개인 도시가 짝수 개라는 사실로 왕을 놀라게 한다. 그다음 그 도시들을 둘씩 짝 짓고, 각 쌍 $(u, v)$마다 $u$에서 $v$로 가며 도로를 짝수 개 쓰는 경로를 잡는다. 한 경로에서 같은 도로를 두 번 쓰지 않는다. 서로 다른 경로가 같은 도로를 나누어 쓰지도 않는다. 같은 도시는 여러 번 지나도 된다.

참모는 이 설명이면 왕이 납득하리라 본다. 다만 경로를 직접 고르지 못해 당신에게 도움을 청했다.

첫 줄에 정수 $n$과 $m$이 주어진다 ($2 \le n, m \le 250000$). 각각 도시 수와 도로 수이다. $m$은 짝수이다.

다음 $m$줄에 정수 $a$, $b$가 주어진다 ($1 \le a, b \le n$, $a \ne b$). 도시 $a$와 $b$를 잇는 양방향 도로를 뜻한다. 같은 두 도시를 잇는 도로는 하나뿐이다.

나가는 도로가 홀수 개인 도시가 적어도 하나 있다고 가정해도 된다.

나가는 도로가 홀수 개인 도시 개수를 $k$라 하자. $k$는 짝수이다.

참모의 계획대로 경로를 잡을 수 없으면 한 줄에 NIE를 출력한다.

잡을 수 있으면 $k/2$개 경로를 아래 규칙으로 유일하게 정해 출력한다.

도시 $1$에서 깊이 우선 탐색으로 신장 나무를 만든다. 아직 보지 않은 이웃 도시 중 번호가 가장 작은 도시부터 방문한다. 각 도시 $x$를 복사본 $x_0$, $x_1$ 둘로 나누고, 더미 도시 $0$을 둔다. 원래 도로 각각을 다음처럼 복사본 사이 도로로 옮긴다.

탐색이 도시 $x$에서, 이미 방문했고 방문 시각이 $x$보다 작은 도시 $y$로 가는 도로를 보면 그 도로를 $x_1$과 $y_0$ 사이에 둔다. 나무에서 부모 $p$의 자식 $c$의 부분나무를 끝낸 뒤, 그때까지 $c_1$에 붙은 도로 개수가 홀수이면 나무 도로를 $c_1$과 $p_0$ 사이에 두고, 짝수이면 $c_0$과 $p_1$ 사이에 둔다.

홀수 차수 도시 $u$마다 도시 $0$과 $u_0$을 잇는 더미 도로를 추가한다. 이 새 그래프에서 $0$에서 시작하는 오일러 회로를 찾는다. 쓰지 않은 인접 도로가 여러 개이면 원래 번호가 가장 작은 도로를 택한다. 더미 도로의 번호는 $-1$로 보고, 번호가 같으면 반대쪽 도시 번호가 더 작은 쪽을 택한다.

더미 도로를 회로에서 빼면 짝수 길이 경로 $k/2$개가 남는다. 회로에 나온 순서대로 출력한다.

각 경로 설명은 두 줄이다. 첫째 줄에 시작 도시 $u_i$, 끝 도시 $v_i$, 도로 수 $l_i$를 출력한다. $l_i$는 짝수이다. 둘째 줄에 그 경로가 지나는 도로 번호 $l_i$개를 순서대로 출력한다. 도로는 입력에 나온 순서대로 $1$부터 $m$까지 번호가 매겨진다.