코딩 대회 수십 년사 timer 20s memory 2048MB

스피니(Sphinny)가 대회를 일정에 맞춰 배치하는 기술을 마스터하여 최고의 프로그래밍 참가자가 된 지도 거의 15년이 지났다. 스피니는 코딩 대회와 함께 성장해 이제는 프로그래밍 대회 주최자가 되었고, 그녀가 운영하는 프로그래밍 클럽 리그(Programming Club League, PCL)는 그녀의 도시에서 가장 인기 있는 스포츠이다.

스피니의 도시에는 버스 정류장이 \mathbf{N}개 있고, 급행 버스 노선이 \mathbf{M}개 있다. 각 노선은 서로 다른 두 버스 정류장을 양방향으로 연결하며, 이를 그 노선의 양 끝점(endpoints)이라고 하자. PCL의 인기로 인해, 각 버스 노선의 운전사는 정확히 한 개의 클럽을 응원한다.

스피니는 j번째 대회의 자료를 버스 정류장 \mathbf{P_j}에서 픽업한 뒤, 버스 정류장 \mathbf{C_j}에서 대회를 열어야 한다. 스피니는 주어진 버스 노선들만 이용해 두 정류장 사이를 이동할 수 있다. 정확히 말해, \mathbf{P_j}에서 \mathbf{C_j}로 가는 경로란, 연속한 두 노선이 항상 공통 정류장(끝점)을 하나 이상 가지는 버스 노선들의 목록이다. 또한 경로의 첫 노선은 끝점으로 \mathbf{P_j}를 포함해야 하고, 경로의 마지막 노선은 끝점으로 \mathbf{C_j}를 포함해야 한다. 같은 버스 노선을 한 경로에서 여러 번 사용할 수도 있음에 유의하라. 스피니의 \mathbf{P_j}에서 \mathbf{C_j}로 가는 경로에 운전사가 클럽 c를 응원하는 버스 노선이 하나 이상 포함되어 있다면, 클럽 c는 그 대회에 참가한다. 그렇지 않다면 클럽 c는 그 대회에 참가하지 않는다. 운영상의 이유로, 스피니는 각 대회에 참가하는 클럽의 수가 홀수이기를 원한다.

스피니의 도시의 버스 노선 구조와 대회 정보가 주어질 때, 참가하는 클럽의 수가 홀수가 되도록 보장할 수 있는 경로를 스피니가 선택할 수 있는 대회의 개수를 구하라.