1830 . 賣萌大賽
TopCoder
Tags
Description
有$n$個蘿莉參加了一場賣萌大賽。這個賣萌大賽的賽制採積分回合賽制，並包含了$m$個回合。規則如下：
每一個回合都會指定兩個蘿莉上台，看看誰比較會賣萌。每一回合都會進行「顏值比拼」和「撒嬌比賽」兩種：在「顏值比併」中，贏家會被加1分積分、輸家會被扣1分積分；然而，做為一個蘿莉，會撒嬌比較重要，因此在「撒嬌比賽」中，輸贏家獲得或失去的分數都雙倍計算。
身為比賽裁判的你，在看著蘿莉們賣萌而流口水之際，也不想要讓任何蘿莉因為分數太高而驕傲地轉變成御姐屬性，更不想要任何蘿莉因為分數太低而傷心欲絕。所以你想要盡可能地將所有蘿莉的分數控制在-1到1之間。當然，裁判，也就是你，有權力決定每一個回合的勝負。
雖然這看起來不一定可行，不過聰明的你發現每個蘿莉所參加的回合權重和都是奇數。你可以寫一個程式安排比賽的勝負嗎？
Input Format
第一行有兩個正整數n, m，分別代表蘿莉的個數和賣萌大賽的回合數。這n個蘿莉從0編號到n-1。
接下來的m行，每行有三個整數ai, bi, ki，依序參加第i回合比賽的蘿莉ai和bi，以及本回合的的回合種類ki：1代表「顏值比併」、2代表「撒嬌大賽」。
對於所有測資，$2\leq n\leq 10^ 6; \frac{n}{2}\leq m\leq 10^ 6;$
$0\leq a_i < b_i \leq n-1; 1\leq k_i\leq 2$。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0~4) | $m\leq 20$ | 11 |
| 2 (5~10) | $n\leq 4$ | 7 |
| 3(11~14) | 沒有撒嬌比賽 | 14 |
| 4(15~19) | 每個蘿莉參加的回合數至多為2 | 28 |
| 5 (20~24) | 無 | 40 |
Output Format
請輸出1行包含m個0或1的字串。如果第i個字元是0，代表第i回合的贏家是ai；反之，如果第i個字元是1，代表第i回合的贏家是bi。
你可以假設本題一定有解。
當然，解不一定是唯一的，你只要輸出一組滿足條件的解就可以了。
Sample Input 1
0 1 1
0 2 1
0 3 1
1 2 1
1 3 1
2 3 1
0 1 2
2 3 2
Sample Output 1
Hints
對於範例輸出所示的安排方法，0的積分為-1、1的積分為1、2的積分為-1、3的積分為1。
當然，不只有這一種安排方法。
Problem Source
Problem set / Description by Paupière
建國中學105學年度校隊選拔：複試pF
題目取自USATST2011p2:
https://www.artofproblemsolving.com/community/c6h420424p2374799
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~4 | 11 |
| 2 | 5~10 | 7 |
| 3 | 11~14 | 14 |
| 4 | 15~19 | 28 |
| 5 | 20~24 | 40 |