도로 청소

N개의 도시로 이루어진 나라가 있고, 도시는 1번부터 N번까지 번호가 붙어있다. 그리고 서로 다른 두 도시를 이어주는 양방향 도로 M개가 있고, 도로도 1번부터 M번까지 번호가 매겨져 있다. 두 도시 사이에 도로가 여러 개 있을 수 있다.

최근에 예산이 모자라는 상황이 발생해 도로 청소차를 두 대만 운영하기로 했다. 이 청소차를 이용해 모든 도로를 한 번씩만 청소하려고 한다.

두 청소차는 각각 임의의 도시에서 출발한다. 같은 도시에서 출발할 수도 있고, 다른 도시에서 출발할 수도 있다. 모든 도로를 정확히 한 번씩만 청소하기 위해, 각 도로는 둘 중 딱 한 대의 청소차만 지나가야 한다 (청소차가 청소를 하지 않고 도로를 그냥 지나갈 수는 없다). 마지막으로, 각 청소차는 하나 이상의 도로를 청소해야 한다 (그렇지 않으면 청소차를 두 대 운영할 이유가 없다).

도시의 도로 정보가 주어졌을 때, 두 대의 청소차를 이용해 모든 도시를 청소할 수 있는지 없는지, 있는 경우 어떻게 청소차가 방문해야 하는지 구해보자.

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스의 첫째 줄에는 도시의 수 N, 도로의 수 M이 주어진다. 둘째 줄과 셋째 줄에 각각 M개의 정수가 주어지며, i번째 정수 쌍이 i번 도로로 이어진 두 도시를 의미한다.

임의의 한 도시에서 다른 모든 도시로 갈 수 있는 경우만 입력으로 주어진다.

각각의 테스트 케이스마다 두 줄을 출력해야 한다.

각 줄에 출력하는 첫 번째 정수는 각 청소차가 청소해야 하는 도로의 수이며, 이후 청소해야 하는 도로의 번호를 순서대로 출력한다. i번 도로가 입력으로 주어진 순서의 반대로 이동하는 경우에는 -i로 출력한다.

모든 도로를 청소하는 것이 불가능한 경우에는 각 줄에 0을 출력한다 (즉 두 줄에 걸쳐 각 줄에 0을 출력한다).

• 1 ≤ N ≤ 1,000
• 1 ≤ M ≤ 50,000