17434번 - 도로 청소 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 256 MB | 262 | 71 | 22 | 22.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
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호