평면 최대 컷

어떤 그래프에서 최소 컷을 찾는 방법은 많이들 알고 있을 것이다. 최대 컷 문제가 NP-완전이라는 사실도 알려져 있다(정확히는 절단 값이 최소 $k$ 이상인 컷이 존재하는지 판별하는 결정 문제가 NP-완전이다). 그러나 그래프가 특정한 형태로 제한되면 일반적인 경우보다 문제가 쉬워질 수 있다.

평면 최대 컷 문제를 생각해 보자. 무방향 그래프 $G$는 정점 $n$개와 간선 $m$개로 이루어져 있고, 정점 집합은 $V = \{v_1, \dots, v_n\}$이다. 이 그래프는 평면 그래프이며, 그 임베딩이 주어진다. 모든 정점의 좌표는 알려져 있고, 간선을 선분으로 그렸을 때 두 간선이 내부 점을 공유하지 않는다. 간선 $j$에는 정수 비용 $c_j$가 붙어 있다.

정점 집합을 서로소인 두 집합 $A$와 $B$로 나누되($A \cup B = V$), 잘린 간선의 비용 합이 최대가 되도록 하라. 간선의 한쪽 끝점은 $A$에, 다른 쪽 끝점은 $B$에 속하면 그 간선을 잘린 간선이라고 한다.

첫 줄에 정점 수 $n$과 간선 수 $m$이 주어진다($1 \le n \le 200$, $1 \le m \le 1000$).

다음 $n$개 줄에는 정점 $i$의 좌표 $x_i$와 $y_i$가 주어진다($-10^4 \le x_i, y_i \le 10^4$). 두 점의 좌표는 겹치지 않는다.

다음 $m$개 줄에는 간선 $j$의 정보 $a_j$, $b_j$, $c_j$가 주어진다($1 \le a_j, b_j \le n$, $a_j \ne b_j$, $0 \le c_j \le 10^5$). 간선 $j$가 정점 $a_j$와 $b_j$를 잇고 비용이 $c_j$라는 뜻이다.

첫 줄에 잘린 간선 비용 합의 최댓값을 출력한다.

둘째 줄에 정수 $n$개 $s_1, s_2, \dots, s_n$을 출력한다. 정점 $i$가 $A$에 속하면 $s_i = 0$, $B$에 속하면 $s_i = 1$이다. 답이 여럿이면 그중 아무거나 출력한다.