题目大意

给定若干条指令（最多 100 条），每条指令可能依赖于其他指令。指令之间的依赖关系用 PRO-CON 关系表示，其中 PRO 表示生产者指令，CON 表示消费者指令，依赖的延迟时间（latency）也随之给出。任务是计算每条指令的优先级，并根据优先级进行排序

题目思路

这道题主要涉及 拓扑排序 和 动态规划 的结合应用。具体步骤如下：

1.建立图模型：

将每条指令看作图中的一个节点。

题目内容

小明最近在做一个工程，工程里面有很多的指令，假设指令 $A$ ： $a= 1$ ；指令 $B$ ： $b=2\times a$ ；

$A$ 指令define了变量 $a$ ， $B$ 指令 $use$ 了变量 $a$ , 我们称 $A$ 为 $PRO(producer)$ ， $B$ 为 $CON (consumer)$ ，他们之间的延时称为 $latency$

若 $A$ 和 $B$ 之间有多条依赖，取最大的 $Iatency$ , $PRIORITY (A)$ 表示指令 $A$ 的优先级，其计算公式如下： $PRIORITY(A)= PRIORITY(B) + latency$ ；

若 $A$ 有多个 $CON (B1, B2)$ ，其 $lategcy$ 分别为 $(L1,L2)$ ： $PRIORITY(A)= max (PRIORITY(B1)+ L1, PRIORITY(B2)+L2)$ ；

若 $A$ 没有 $CON$ : $PRIORITY(A)=0$ ；

现有若干条指令(数据依赖没有环)，编号分别为 $1,2,...,n$ 现需要根据其 $PRIORITY$ 对其进行排序，若两条指令的 $PRIORITY$ 相同，则根据其编号先后进行排序。

输入描述

第一行：指令数 $n$ (最大不超过 $100$ )， 关系行数 $m$ (最大不超过 $500$ )

第 $2 一m+1$ 行： $PRO-CON$ 关系，如 $(1\ 2\ 4)$ 表示编号 $1$ 和编号 $2$ 指令存在 $PRO-CON$ 关系，其 $latency=4$

输出描述

输出最终的排序编号： $1\ 2\ 3$

样例

样例一：

输入

4 3
1 2 1
2 3 1
3 4 2

输出

1 2 3 4

样例二：

输入

3 3
1 2 1
3 1 2
3 2 1

输出

3 1 2