Parity Constraint Perfect Matching

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

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

Perfect Matching은 간선의 양 끝점이 겹치지 않도록 고른 $N$개의 간선의 집합이다. 간선 가중치의 합이 짝수인 Perfect Matching과 홀수인 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을 출력한다.

두 번째 줄부터는 같은 방식으로 가중치 합이 홀수인 Perfect Matching을 출력한다. 마찬가지로 존재하지 않으면 -1을 출력한다.

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