[Balkan2012]Fan Groups

时间限制：2s 空间限制：128MB

题目描述

给定一个有向图，每个节点关联于一群人。这N群人按照某个特定的顺序进行以下操作：
到达并占领他们关联的节点；
从他们占领的某个节点u出发，走到与其相邻的每个点v。如果点v已经被人占领，他们会边(u,v)上发生冲突，并不再在这个方向上前进；否则，他们会占领点v，并重复这一步，直到没有能到达的点为止。
如果他们关联的节点在此前被别的人群占领，他们不会与那群人发生冲突。在这种情况下，他们什么都不做。
给定该图，以及发生冲突的边集。求一种人群的行动顺序，使得发生冲突的边集与输入相符。
以样例为例。关联于点8的人群首先行动，占领点8；接下来关联于点5的人群行动，占领点4,5,6（与4相连的点集）；关联于点6的人群出动，因为点6已经被占领，他们什么都不做；人群2占领点2,3；人群3什么都不做；人群1占领点1，并在边<1,4>和<1,8>上引发冲突；人群7占领点7并在边<7,1>和<7,4>上引发冲突；人群4什么都不做。
注意合法的顺序可能不止一种；样例中，(2, 3, 8, 4, 1, 7, 5, 6)也是一种合法的方案。注意(8, 5, 6, 3, 2, 1, 7, 4)不是合法的方案，因为按照这个方案，<2,3>上也会发生冲突，与输入不符。

输入格式

输入的第一行包含两个整数N,M，含义是点数和边数。
接下来M行，每行三个整数A,B,C，表示有向边A->B，如果C=1，则这条边上发生了冲突。
N<=20000,M<=200000。

输出格式

输出一个排列，表示人群的行动顺序。
如果没有任何顺序满足题意，输出-1。

样例输入

样例输出

8 5 6 2 3 1 7 4

提示

Dragonite提供SPJ

题目来源

没有写明来源