有一个排列。有(m)个三元组((a_i,b_i,c_i))，表示(b_i)的位置在(a_i)的位置和(c_i)的位置之间（不确定(a_i)和(c_i)的位置关系），满足这个排列。
你现在需要尽可能地还原这个排列，使得有至少一半的三元组被满足。
(n,mle 10^5)
做不出来的神仙构造。。
首先整一个类似于拓扑序的东西，使得(a_i)和(c_i)一定不同时出现在(b_i)前。因为一定有解，所以这个序一定存在。
从后往前扫，构造答案序列。对于一个三元组，在最前面一个位置（即扫到的最后一个位置）统计贡献。设这个位置上的是(a)，三元组((a,b,c))可能存在答案序列中(b)在(c)前和(b)在(c)后两种情况，可以算出(a)放最左边的贡献和最右边的贡献。贪心决定取哪边，并且将(a)丢到那一边。
由于贪心地取，所以每次至少一半被满足。
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <list>
#define N 100005
int n,m;
struct EDGE{
int b,c;
EDGE *las;
} e[N*2];
int ne;
EDGE *last[N];
int in[N],vis[N];
int q[N],t[N];
void init(){
int head=1,tail=0;
for (int i=1;i<=n;++i)
if (!in[i])
q[++tail]=i;
while (head<=tail){
int a=q[head++];
vis[a]=1;
for (EDGE *ei=last[a];ei;ei=ei->las)
if (!vis[ei->c]){
if (!--in[ei->b])
q[++tail]=ei->b;
}
}
for (int i=1;i<=n;++i)
t[q[i]]=i;
}
int _ans[N*2],*ans=_ans+N,l,r,w[N];
int main(){
freopen("in.txt","r",stdin);
scanf("%d%d",&n,&m);
for (int i=1;i<=m;++i){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
e[ne]={b,c,last[a]};
last[a]=e+ne++;
e[ne]={b,a,last[c]};
last[c]=e+ne++;
in[b]++;
}
init();
ans[l=r=0]=q[n];
w[q[n]]=l;
for (int i=n-1;i>=1;--i){
int a=q[i],mn=0,mx=0;
for (EDGE *ei=last[a];ei;ei=ei->las)
if (t[ei->c]>t[a]){
if (w[ei->b]<w[ei->c])
mn++;
else
mx++;
}
if (mn>mx){
ans[--l]=a;
w[a]=l;
}
else{
ans[++r]=a;
w[a]=r;
}
}
for (int i=l;i<=r;++i)
printf("%d ",ans[i]);
return 0;
}