Estimate Order

题目描述

有 $N$ 个人，编号为 $1$ 到 $N$。 在这 $N$ 个人之间举行了一场比赛，他们据此被排出名次。关于他们的名次给出了以下信息：

每个人的名次都互不相同。 对于每个 $1 \leq i \leq M$，如果人 $A_i$ 的名次为第 $x$ 位而人 $B_i$ 的名次为第 $y$ 位，则有 $x - y = C_i$。

给定的输入保证至少存在一种不与给定信息矛盾的可能排名。 回答 $N$ 个查询。第 $i$ 个查询的答案按如下方式确定为整数：

如果第 $i$ 个人的名次可以被唯一确定，则返回该名次。否则，返回 $-1$。

输入格式

输入由标准输入按以下格式给出： $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$ 个查询的答案，答案之间用空格隔开。

5 2
2 3 3
5 4 3

3 -1 -1 -1 -1

3 0

-1 -1 -1

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

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

提示

$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)$ 至少存在一种不与给定信息矛盾的可能排名。 所有输入值均为整数。令 $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$。

标签: AtCoder|abc352F

来源

AtCoder|abc352F