정점 \(N\)개, 간선 \(M\)개의 방향 다중 그래프가 주어진다(다중 간선·자기 간선 가능). 모든 간선을 정확히 한 번씩 지나 시작점으로 되돌아오는 오일러 회로가 존재하는지 판정한다.

오일러 회로가 존재하면 사용된 간선의 수(즉 \(M\))를 출력하고, 존재하지 않으면 -1을 출력하라. 간선이 전혀 없는 경우 답은 0이다.

(방향 그래프의 오일러 회로 조건: 간선이 있는 모든 정점에서 진입차수 = 진출차수이고, 간선이 있는 정점들이 하나의 강연결 요소를 이룬다.)

\(1 \le N \le 100{,}000\)
\(0 \le M \le 200{,}000\)
\(1 \le u, v \le N\) (자기 간선·다중 간선 허용)

첫 줄에 \(N\), \(M\).
이후 \(M\)줄에 방향 간선 \(u\ v\) (다중·자기 간선 가능).

오일러 회로가 존재하면 간선 수를, 아니면 -1을 출력한다.

riseoj 작성

출처 Original