시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 3 3 1 100.000%

문제

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

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

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

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

입력

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

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

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

출력

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

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

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

제한

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

예제 입력 1

5
4 5
1 1 1 2 3
2 2 3 4 4
4 5
1 1 1 2 3
2 2 3 4 4
4 3
1 1 1
2 3 4
6 5
1 1 1 1 1
2 3 4 5 6
2 1
2
1

예제 출력 1

1 1
4 2 4 -5 -3
2 3 5
3 -1 2 4
2 -1 3
1 -2
0
0
0
0
W3sicHJvYmxlbV9pZCI6IjE3NDM0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViM2M0XHViODVjIFx1Y2NhZFx1YzE4YyIsImRlc2NyaXB0aW9uIjoiPHA+Tlx1YWMxY1x1Yzc1OCBcdWIzYzRcdWMyZGNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YjA5OFx1Yjc3Y1x1YWMwMCBcdWM3ODhcdWFjZTAsIFx1YjNjNFx1YzJkY1x1YjI5NCAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YmQ5OVx1YzViNFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViNDUwIFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWM3NzRcdWM1YjRcdWM4ZmNcdWIyOTQgXHVjNTkxXHViYzI5XHVkNWE1IFx1YjNjNFx1Yjg1YyBNXHVhYzFjXHVhYzAwIFx1Yzc4OFx1YWNlMCwgXHViM2M0XHViODVjXHViM2M0IDFcdWJjODhcdWJkODBcdWQxMzAmbmJzcDtNXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LiBcdWI0NTAgXHViM2M0XHVjMmRjIFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWIzYzRcdWI4NWNcdWFjMDAgXHVjNWVjXHViN2VjIFx1YWMxYyBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjZDVjXHVhZGZjXHVjNWQwIFx1YzYwOFx1YzBiMFx1Yzc3NCBcdWJhYThcdWM3OTBcdWI3N2NcdWIyOTQgXHVjMGMxXHVkNjY5XHVjNzc0IFx1YmMxY1x1YzBkZFx1ZDU3NCBcdWIzYzRcdWI4NWMgXHVjY2FkXHVjMThjXHVjYzI4XHViOTdjIFx1YjQ1MCBcdWIzMDBcdWI5Y2MgXHVjNmI0XHVjNjAxXHVkNTU4XHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC4gXHVjNzc0IFx1Y2NhZFx1YzE4Y1x1Y2MyOFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzQgXHViYWE4XHViNGUwIFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWQ1NWMgXHViYzg4XHVjNTI5XHViOWNjIFx1Y2NhZFx1YzE4Y1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWNjYWRcdWMxOGNcdWNjMjhcdWIyOTQgXHVhYzAxXHVhYzAxIFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWIzYzRcdWMyZGNcdWM1ZDBcdWMxMWMgXHVjZDljXHViYzFjXHVkNTVjXHViMmU0LiBcdWFjMTlcdWM3NDAgXHViM2M0XHVjMmRjXHVjNWQwXHVjMTFjIFx1Y2Q5Y1x1YmMxY1x1ZDU2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHVhY2UwLCBcdWIyZTRcdWI5NzggXHViM2M0XHVjMmRjXHVjNWQwXHVjMTFjIFx1Y2Q5Y1x1YmMxY1x1ZDU2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWJhYThcdWI0ZTAgXHViM2M0XHViODVjXHViOTdjIFx1YzgxNVx1ZDY1NVx1ZDc4OCBcdWQ1NWMgXHViYzg4XHVjNTI5XHViOWNjIFx1Y2NhZFx1YzE4Y1x1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQsIFx1YWMwMSBcdWIzYzRcdWI4NWNcdWIyOTQmbmJzcDtcdWI0NTggXHVjOTExIFx1YjUzMSBcdWQ1NWMgXHViMzAwXHVjNzU4IFx1Y2NhZFx1YzE4Y1x1Y2MyOFx1YjljYyBcdWM5YzBcdWIwOThcdWFjMDBcdWM1N2MgXHVkNTVjXHViMmU0IChcdWNjYWRcdWMxOGNcdWNjMjhcdWFjMDAgXHVjY2FkXHVjMThjXHViOTdjIFx1ZDU1OFx1YzljMCBcdWM1NGFcdWFjZTAgXHViM2M0XHViODVjXHViOTdjIFx1YWRmOFx1YjBlNSBcdWM5YzBcdWIwOThcdWFjMDggXHVjMjE4XHViMjk0IFx1YzVjNlx1YjJlNCkuIFx1YjljOFx1YzljMFx1YjljOVx1YzczY1x1Yjg1YywgXHVhYzAxIFx1Y2NhZFx1YzE4Y1x1Y2MyOFx1YjI5NCBcdWQ1NThcdWIwOTggXHVjNzc0XHVjMGMxXHVjNzU4IFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWNjYWRcdWMxOGNcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0IChcdWFkZjhcdWI4MDdcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTc0IFx1Y2NhZFx1YzE4Y1x1Y2MyOFx1Yjk3YyBcdWI0NTAgXHViMzAwIFx1YzZiNFx1YzYwMVx1ZDU2MCBcdWM3NzRcdWM3MjBcdWFjMDAgXHVjNWM2XHViMmU0KS48XC9wPlxyXG5cclxuPHA+XHViM2M0XHVjMmRjXHVjNzU4IFx1YjNjNFx1Yjg1YyBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViNDUwIFx1YjMwMFx1Yzc1OCBcdWNjYWRcdWMxOGNcdWNjMjhcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTc0IFx1YmFhOFx1YjRlMCBcdWIzYzRcdWMyZGNcdWI5N2MgXHVjY2FkXHVjMThjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjNWM2XHViMjk0XHVjOWMwLCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwIFx1YzViNFx1YjViYlx1YWM4YyBcdWNjYWRcdWMxOGNcdWNjMjhcdWFjMDAgXHViYzI5XHViYjM4XHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NzRcdWJjZjRcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWMyMTggTiwgXHViM2M0XHViODVjXHVjNzU4IFx1YzIxOCBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YWNmYyBcdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWMwMVx1YWMwMSBNXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIGlcdWJjODhcdWM5ZjggXHVjODE1XHVjMjE4IFx1YzMwZFx1Yzc3NCBpXHViYzg4IFx1YjNjNFx1Yjg1Y1x1Yjg1YyBcdWM3NzRcdWM1YjRcdWM5YzQgXHViNDUwIFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWQ1NWMgXHViM2M0XHVjMmRjXHVjNWQwXHVjMTFjIFx1YjJlNFx1Yjk3OCBcdWJhYThcdWI0ZTAmbmJzcDtcdWIzYzRcdWMyZGNcdWI4NWMgXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHViOWNjIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHViNDUwIFx1YzkwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVjOTA0XHVjNWQwIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzgxNVx1YzIxOFx1YjI5NCZuYnNwO1x1YWMwMSBcdWNjYWRcdWMxOGNcdWNjMjhcdWFjMDAgXHVjY2FkXHVjMThjXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWIzYzRcdWI4NWNcdWM3NTggXHVjMjE4XHVjNzc0XHViYTcwLCBcdWM3NzRcdWQ2YzQgXHVjY2FkXHVjMThjXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWIzYzRcdWI4NWNcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIGlcdWJjODggXHViM2M0XHViODVjXHVhYzAwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMjFjXHVjMTFjXHVjNzU4IFx1YmMxOFx1YjMwMFx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IC1pXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWNjYWRcdWMxOGNcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YzkwNFx1YzVkMCAwXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNCAoXHVjOTg5IFx1YjQ1MCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YWMwMSBcdWM5MDRcdWM1ZDAgMFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQpLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgTiAmbGU7IDEsMDAwPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBNICZsZTsgNTAsMDAwPFwvbGk+XHJcbjxcL3VsPlxyXG4ifSx7InByb2JsZW1faWQiOiIxNzQzNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlN0cmVldCBDbGVhbmluZyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlcmUgaXMgYSBjb3VudHJ5IHRoYXQgaGFzIE4gY2l0aWVzIGFuZCB0aGUgY2l0aWVzIGFyZSBudW1iZXJlZCBmcm9tIDEgdG8gTi4gVGhlcmUgYXJlIE0gYmktZGlyZWN0aW9uYWwgc3RyZWV0cyBlYWNoIG9mIHdoaWNoIGNvbm5lY3RzIHR3byBkaXN0aW5jdCBjaXRpZXMsIHRoZSBzdHJlZXRzIGFyZSBudW1iZXJlZCBmcm9tIDEgdG8gTS4gVGhlcmUgbWF5IGV4aXN0IG11bHRpcGxlIHN0cmVldHMgYmV0d2VlbiB0aGUgc2FtZSBwYWlyIG9mIGNpdGllcy48XC9wPlxyXG5cclxuPHA+RHVlIHRvIGEgcmVjZW50IGJ1ZGdldCBjb25zdHJhaW50LCB0aGUgZ292ZXJubWVudCBoYXMgZGVjaWRlZCB0byBvcGVyYXRlIG9ubHkgdHdvIHN0cmVldCBjbGVhbmluZyB2ZWhpY2xlcy4gVXNpbmcgdGhlc2UgdHdvIHZlaGljbGVzLCB5b3Ugd2lzaCB0byBjbGVhbiBlYWNoIHN0cmVldCBleGFjdGx5IG9uY2UuPFwvcD5cclxuXHJcbjxwPkVhY2ggdmVoaWNsZSBjYW4gc3RhcnQgY2xlYW5pbmcgZnJvbSBhbnkgY2l0eSB5b3UgbGlrZS4gVGhlIHR3byB2ZWhpY2xlcyBtYXkgc3RhcnQgZnJvbSB0aGUgc2FtZSBjaXR5IG9yIGRpZmZlcmVudCBjaXRpZXMuIEluIG9yZGVyIHRvIGNsZWFuIGVhY2ggc3RyZWV0IGV4YWN0bHkgb25jZSwgZXZlcnkgc3RyZWV0IG11c3QgYmUgdHJhdmVyc2VkIGJ5IGV4YWN0bHkgb25lIHZlaGljbGUgYmVjYXVzZSZuYnNwO2EmbmJzcDtjbGVhbmluZyB2ZWhpY2xlIGNhbm5vdCB0cmF2ZXJzZSB0aGUgc3RyZWV0IHdpdGhvdXQgY2xlYW5pbmcgaXQuIEZpbmFsbHksIGVhY2ggdmVoaWNsZSBtdXN0IGNsZWFuIGF0IGxlYXN0IG9uZSByb2FkIChvdGhlcndpc2Ugd2UgaGF2ZSBubyByZWFzb24gdG8ga2VlcCBib3RoIHZlaGljbGVzKS48XC9wPlxyXG5cclxuPHA+R2l2ZW4gdGhlIGNpdHkgYW5kIHN0cmVldCBpbmZvcm1hdGlvbiwgZGV0ZXJtaW5lIHdoZXRoZXIgd2UgY2FuIGNsZWFuIGVhY2ggc3RyZWV0IGV4YWN0bHkgb25jZSB1c2luZyB0d28gY2xlYW5pbmcgdmVoaWNsZXMuIElmIHBvc3NpYmxlLCB3ZSBzaG91bGQgYWxzbyBmaW5kIGEgd2F5IHRvIGRvIHNvLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgd2lsbCBjb250YWluIG9uZSBpbnRlZ2VyIFQuPFwvcD5cclxuXHJcbjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgdGhlIGZpcnN0IGxpbmUgd2lsbCBjb250YWluIHR3byBpbnRlZ2VycyBOICh0aGUgbnVtYmVyIG9mIGNpdGllcykgYW5kIE0gKHRoZSBudW1iZXIgb2Ygc3RyZWV0cykuIFRoZSBuZXh0IHR3byBsaW5lcyB3aWxsIGNvbnRhaW4gTSBpbnRlZ2VycyBlYWNoIHNvIHRoYXQgdGhlIGktdGggcGFpciBvZiBpbnRlZ2VycyByZXByZXNlbnQgdGhlIHR3byBjaXRpZXMgY29ubmVjdGVkIGJ5IHRoZSBpLXRoIHN0cmVldC48XC9wPlxyXG5cclxuPHA+RWFjaCB0ZXN0IGNhc2Ugd2lsbCBhbHdheXMgc2F0aXNmeSB0aGUgZm9sbG93aW5nOiBGcm9tIGFueSBjaXR5IHlvdSBjYW4gcmVhY2ggYW55IG90aGVyIGNpdHkgdXNpbmcgdGhlIGdpdmVuIHN0cmVldHMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCB5b3UgbXVzdCBvdXRwdXQgdHdvIGxpbmVzLjxcL3A+XHJcblxyXG48cD5UaGUgZmlyc3QgaW50ZWdlciBpbiBlYWNoIG9mIHRoZSB0d28gbGluZXMgaXMgdGhlIG51bWJlciBvZiBzdHJlZXRzIGEgdmVoaWNsZSBtdXN0IGNsZWFuLCBmb2xsb3dlZCBieSB0aGUgc3RyZWV0IG51bWJlcnMuIElmIHRoZSB2ZWhpY2xlIG11c3QgdHJhdmVyc2UgdGhlIGl0aCBzdHJlZXQgaW4gdGhlIHJldmVyc2VkIG9yZGVyIChjb21wYXJlZCB0byB0aGUgb3JpZ2luYWwgaW5wdXQpLCB0aGVuIG91dHB1dCAtaS48XC9wPlxyXG5cclxuPHA+SWYgaXQgaXMgaW1wb3NzaWJsZSB0byBjbGVhbiBldmVyeSBzdHJlZXQgZXhhY3RseSBvbmNlLCB0aGVuIHlvdSBtdXN0IG91dHB1dCAwIGluIGVhY2ggbGluZSAoaGVuY2UsIHR3byBsaW5lcyB3aXRoIDAgaW4gZWFjaCBsaW5lKS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQiLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IE4gJmxlOyAxLDAwMDxcL2xpPlxyXG5cdDxsaT4xICZsZTsgTSAmbGU7IDUwLDAwMDxcL2xpPlxyXG48XC91bD5cclxuIn1d