103525: [Atcoder]ABC352 F - Estimate Order

Problem Statement

There are $N$ people, numbered $1$ to $N$.

A competition was held among these $N$ people, and they were ranked accordingly. The following information is given about their ranks:

• Each person has a unique rank.
• For each $1 \leq i \leq M$, if person $A_i$ is ranked $x$-th and person $B_i$ is ranked $y$-th, then $x - y = C_i$.

The given input guarantees that there is at least one possible ranking that does not contradict the given information.

Answer $N$ queries. The answer to the $i$-th query is an integer determined as follows:

• If the rank of person $i$ can be uniquely determined, return that rank. Otherwise, return $-1$.

Constraints

• $2 \leq N \leq 16$
• $0 \leq M \leq \frac{N(N - 1)}{2}$
• $1 \leq A_i, B_i \leq N$
• $1 \leq C_i \leq N - 1$
• $(A_i, B_i) \neq (A_j, B_j) (i \neq j)$
• There is at least one possible ranking that does not contradict the given information.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$\vdots$
$A_M$ $B_M$ $C_M$

Output

Print the answers to the $1$-st, $2$-nd, $\ldots$, $N$-th queries in this order, separated by spaces.

Sample Input 1

5 2
2 3 3
5 4 3

Sample Output 1

3 -1 -1 -1 -1

Let $X_i$ be the rank of person $i$. Then, $(X_1, X_2, X_3, X_4, X_5)$ could be $(3, 4, 1, 2, 5)$ or $(3, 5, 2, 1, 4)$.

Therefore, the answer to the $1$-st query is $3$, and the answers to the $2$-nd, $3$-rd, $4$-th, and $5$-th queries are $-1$.

Sample Input 2

3 0

Sample Output 2

-1 -1 -1

Sample Input 3

8 5
6 7 3
8 1 7
4 5 1
7 2 1
6 2 4

Sample Output 3

1 -1 -1 -1 -1 -1 -1 8

问题描述

有 $N$ 个人，编号为 $1$ 到 $N$。

在这 $N$ 个人中举行了一场比赛，并按照比赛成绩进行了排名。关于他们的排名，有以下信息：

• 每个人都有一个唯一的排名。
• 对于每个 $1 \leq i \leq M$，如果编号为 $A_i$ 的人排名为 $x$，编号为 $B_i$ 的人排名为 $y$，则 $x - y = C_i$。

给定的输入保证至少存在一个排名情况，不会与给定信息矛盾。

回答 $N$ 个查询。第 $i$ 个查询的答案是一个整数，确定方式如下：

• 如果编号为 $i$ 的人的排名可以唯一确定，返回该排名。否则，返回 $-1$。

限制条件

• $2 \leq N \leq 16$
• $0 \leq M \leq \frac{N(N - 1)}{2}$
• $1 \leq A_i, B_i \leq N$
• $1 \leq C_i \leq N - 1$
• $(A_i, B_i) \neq (A_j, B_j) (i \neq j)$
• 至少存在一个排名情况，不会与给定信息矛盾。
• 所有输入值都是整数。

输入

输入从标准输入按以下格式给出：

$N$ $M$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$\vdots$
$A_M$ $B_M$ $C_M$

输出

按顺序打印第 $1$、$2$、$\ldots$、$N$ 个查询的答案，用空格分隔。

样例输入1

5 2
2 3 3
5 4 3

样例输出1

3 -1 -1 -1 -1

设 $X_i$ 为编号为 $i$ 的人的排名。那么，$(X_1, X_2, X_3, X_4, X_5)$ 可能是 $(3, 4, 1, 2, 5)$ 或 $(3, 5, 2, 1, 4)$。

因此，第 $1$ 个查询的答案是 $3$，第 $2$、$3$、$4$ 和 $5$ 个查询的答案是 $-1$。

样例输入2

3 0

样例输出2

-1 -1 -1

样例输入3

8 5
6 7 3
8 1 7
4 5 1
7 2 1
6 2 4

样例输出3

1 -1 -1 -1 -1 -1 -1 8