쓰레기 수거

바이트버그의 쓰레기 수거 회사가 요금을 크게 올리자, 일부 주민이 요금 납부를 그만두고 쓰레기를 거리에 버리기 시작했다. 시장 바이트아사르는 주민들이 다시 요금을 내도록 유도하기 위해, 각 거리가 최종적으로 깨끗해야 하는지 아니면 쓰레기로 덮여 있어야 하는지를 정한 계획을 세웠다.

바이트버그에는 교차로가 $n$개, 양방향 거리가 $m$개 있다. 각 거리는 서로 다른 두 교차로를 잇고, 같은 교차로 쌍을 잇는 거리는 두 개 이상 존재하지 않는다. 모든 거리는 현재 깨끗하거나 쓰레기로 덮여 있다.

계획은 쓰레기차의 경로로 수행한다. 하나의 경로는 어떤 교차로에서 출발해 여러 거리를 지나 출발한 교차로로 되돌아온다. 한 경로 안에서는 출발 교차로를 제외한 어떤 교차로도 두 번 이상 지나지 않으며, 출발 교차로만 처음과 끝에서 정확히 두 번 나타난다. 쓰레기차가 어떤 거리를 지날 때마다 그 거리의 상태는 반전된다. 즉, 쓰레기로 덮인 거리는 깨끗해지고, 깨끗한 거리는 쓰레기로 덮인다.

경로는 여러 개를 지시할 수 있고, 한 거리를 둘 이상의 경로가 지날 수도 있다. 중요한 것은 각 거리의 최종 상태뿐이다. 모든 거리를 목표 상태로 만들기 위해 필요한 총 주행량(지나는 거리의 수)의 최솟값을 구하거나, 계획을 실행할 수 없음을 판별하라.

첫째 줄에 두 정수 $n$과 $m$이 공백으로 구분되어 주어진다 ($1 \le n \le 100000$, $1 \le m \le 1000000$). 각각 교차로의 수와 거리의 수를 뜻한다. 교차로는 $1$번부터 $n$번까지 번호가 매겨져 있다.

다음 $m$개의 줄에는 각각 네 정수 $a$, $b$, $s$, $t$가 공백으로 구분되어 주어진다 ($1 \le a < b \le n$, $s, t \in \{0, 1\}$). 이는 교차로 $a$와 $b$를 잇는 거리가 있으며, $s$는 그 거리의 현재 상태, $t$는 목표 상태임을 뜻한다. $0$은 깨끗함을, $1$은 쓰레기로 덮여 있음을 뜻한다.

정수 하나를 출력한다. 모든 거리를 목표 상태로 만들기 위해 필요한 총 주행량의 최솟값, 즉 모든 경로에 걸쳐 거리를 한 번 지날 때마다 $1$로 세었을 때의 합의 최솟값을 출력한다. 계획을 실행할 수 있는 경로 집합이 존재하지 않으면 대신 $-1$을 출력한다.