「Stoi2029」以父之名

> 以父之名判决 > 那感觉没有适合字汇 > 就像边笑边掉泪 > 凝视着完全的黑 > 阻挡悲剧蔓延的悲剧会让我沉醉 > ——《[以父之名](https://www.bilibili.com/video/BV1fx411N7bU?p=36)》

地狱里有 $n$ 个罪人在等待判决，编号为 $1$ 至 $n$。罪人们之间有 $m$ 条罪的联系，编号为 $1$ 至 $m$，每条联系 的值为 $1$ 或 $2$ 且恰好连接两个罪人。 称一个罪人的自负度为他和其他所有罪人之间联系的值之和。两个罪人之间可能不止有一条联系，此时这些联系的值都应该被计算。由于这些罪人承受了太多的罪恶，他们变得不和谐。具体地，每个罪人的自负度都是奇数。 现在，神明将要对他们进行判决。判决的具体方式为：将每条联系都进行定向，使得这条联系所连接的两个罪人中的一个受到惩罚，另一个受到救赎，它们的值均为这条联系的值。 由于神明秉承父的仁慈，希望罪人们更加均等地接受惩罚和救赎，于是他规定判决后每个罪人所受到的惩罚和救赎值总和之差的绝对值必须恰好为 $1$。 由于神明工作繁忙，因此他以父之名要求你为他找到一种判决的方法。由于父的指示不会有错，所以一定存在一种这样的方法。 --- #### 题意简述 给定一个 $n$ 个点 $m$ 条边的无向图，边权均为 $1$ 或 $2$。保证每个点所相连的边权值之和均为奇数。你需要将这些边定向，使每个点的入边权值和与出边权值和之差的绝对值恰为 $1$。保证有解。输出任意一种方案。

第一行两个正整数：$n,m$，表示有 $n$ 个罪人和 $m$ 条罪的联系。 接下来 $m$ 行，第 $i+1$ 行为三个正整数：$u_i,v_i,w_i$，表示第 $i$ 条联系连接 $u_i$ 与 $v_i$ 且值为 $w_i$。

共一行 $m$ 个数字，第 $i$ 个数字为 $0$ 表示使 $u_i$ 受到惩罚，使 $v_i$ 受到救赎；为 $1$ 表示使 $v_i$ 受到惩罚，使 $u_i$ 受到救赎。

4 5
1 2 1
1 3 2
2 3 1
2 4 1
4 1 2

00100

#### 样例解释 定向后的图如下：  更多样例详见题目附件 `trial_sample.zip`。 ------ #### 数据范围 **本题采用捆绑测试。** - 特殊性质 A：边权均为 $1$，且任意两点之间只存在一条简单路径，且没有重边。 - 特殊性质 B：同一个点至多只有一条边权为 $1$ 和一条边权为 $2$ 的边相连。 | Subtask | 分值 | $1\le n \le$ | $1\le m \le$ | 特殊性质 | | :-: | :-: | :-: | :-: | :-: | | $1$ | $7$ | $10$ | $15$ | 无 | | $2$ | $20$ |$10^3$ | $3\times10^3$ | 无 | | $3$ | $20$ |$3 \times 10^5$ | $3 \times 10^5$ | A | | $4$ | $20$ |$3 \times 10^5$ | $3 \times 10^5$ | B | | $5$ | $33$ |$10^6$ | $3 \times 10^6$ | 无 | 对于 $100\%$ 的数据，$1 \le u_i,v_i \le n \le 10^6$，$1 \le m \le 3 \times 10^6$，$w_i \in \{1,2\}$。 在题目附件 `trial_sample.zip` 中： - `trial_sample1.in` 即为样例 #1。 - `trial_sample2.in` 满足特殊性质 A。 - `trial_sample3.in` 满足特殊性质 B。 - `trial_sample4.in` 不满足特殊性质。 另外该目录下还有 `checker.exe`。 ------ #### 提示 **本题输入输出量较大，请使用较快的输入输出方式。** 本题提供 [Special Judge 源码](https://www.luogu.com.cn/paste/7albhubs)和 `checker.exe`，供选手调试。Windows 下使用方法为: 命令行在目标文件夹输入指令： ``` checker.exe data.in data.out data.out ``` 其中 `data.in` 是输入数据文件，`data.out` 是程序运行结果文件。观察评判结果即可。 - `Perfect answer.` 表示答案正确。 - `Wrong answer on node x, and the difference is d.` 表示答案错误，其中节点 $x$ 的入边权值和与出边权值和之差的绝对值为 $d$ 而不为 $1$。 - `Invalid answer.` 表示输出的字符串长度不正确或输出非法字符。 请务必保证**输出格式正确**，否则 Special Judge 可能会返回 Unknown Error 等不可预估的结果。