← 返回题目列表

AtCoder · abc352_f

I. 预估订单

中文机器翻译题面 查看原题

分数: 525 点

问题陈述

有 N 人,已编号 1 to N.

在这些人之间举行了一场比赛 N 人,并且他们被相应地排名。以下是有关他们的排名的信息:

  • 每个人都有一个独特的等级。
  • 对于每个 1 \leq i \leq M,如果人 A_i 排名 x-th 和人 B_i 排名 y-th,然后 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-st, 2-nd, \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) or (3, 5, 2, 1, 4).

因此,答案 1-st 查询是 3,以及问题的答案 2-nd, 3-rd, 选择 4-th,以及 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