레이팅 미적용설명
정점 \(N\)개, 간선 \(M\)개의 무방향 다중 그래프가 주어진다. 다중 간선과 자기 간선이 존재할 수 있다. (자기 간선은 해당 정점의 차수를 2 증가시킨다.)
간선이 하나 이상인 모든 정점이 한 연결 요소에 속하고:
- 홀수 차수 정점이 없으면 오일러 회로가 존재한다 → 회로
- 홀수 차수 정점이 정확히 2개이면 오일러 경로만 존재한다 → 경로
- 그 외(연결되지 않았거나 홀수 차수 정점이 2개 초과)면 → 불가능
간선이 전혀 없는 경우는 회로로 간주한다. 알맞은 토큰을 출력하라.
제약
\(1 \le N \le 100{,}000\)
\(0 \le M \le 200{,}000\)
\(1 \le u, v \le N\) (자기 간선·다중 간선 허용)
입력 형식
첫 줄에 \(N\), \(M\).
이후 \(M\)줄에 무방향 간선 \(u\ v\) (다중·자기 간선 가능).
출력 형식
회로, 경로, 불가능 중 하나를 출력한다.
예제 1
입력
4 4
1 2
2 3
3 4
4 1
출력
회로설명
사각형 1-2-3-4-1. 모든 정점 차수 2(짝수)이고 연결 → 오일러 회로 → 회로.
예제 2
입력
3 2
1 2
2 3
출력
경로설명
경로 1-2-3. 정점 1과 3의 차수가 1(홀수) 2개 → 오일러 경로만 존재 → 경로.
문제 정보
riseoj 작성
출처 Original
태그