20935번 - Parity Constraint Perfect Matching 스페셜 저지

국렬이는 졸업하신 선배님을 존경하는 마음에 Parity Constraint 문제를 더 내려고 한다.

왼쪽과 오른쪽 정점이 각각 $N$개가 있고, 가중치가 있는 간선 $M$개로 구성된 이분 그래프가 주어진다. 왼쪽 정점과 오른쪽 정점에는 각각 $1$부터 $N$까지 번호가 매겨져 있고, 서로 다른 두 정점 사이에는 최대 한 개의 간선이 존재한다.

Perfect Matching은 간선의 양 끝점이 중복되지 않게 선택한 $N$개의 간선의 집합을 의미한다. 간선의 가중치의 합이 짝수, 홀수인 Perfect Matching을 각각 구해보자.

첫째 줄에는 $N$과 $M$이 주어진다. ($1 \le N \le 500$, $1 \le M \le N^2$)

다음 $M$개의 줄에 걸쳐서 간선을 나타내는 $(x, y, c)$가 순서대로 주어진다. $x$는 왼쪽 정점의 번호, $y$는 오른쪽 정점의 번호, $c$는 간선의 가중치를 의미한다. ($1 \le x, y \le N$, $1 \le c \le 10^9$) 두 정점 사이에 간선이 여러 개가 있는 경우는 존재하지 않는다.

첫째 줄부터 $N$개의 줄에 걸쳐 간선의 가중치의 합이 짝수인 Perfect Matching에 속한 간선의 양 끝점의 번호를 왼쪽과 오른쪽 순으로 출력한다. 짝수 Perfect Matching이 존재하지 않는 경우 -1을 출력한다.

두 번째 줄부터 $N$개에 줄에 걸쳐 간선의 가중치의 합이 홀수인 Perfect Matching도 같은 방식으로 출력한다. 마찬가지로 존재하지 않는 경우 -1을 출력한다.

가중치의 합이 최소일 필요는 없으며 간선의 출력 순서는 상관없다. 답이 여러 개인 경우 아무것이나 출력해도 된다.