Description：

给一个正整数序列 $a$ ，已知 $s$ 个数，给出 $m$ 条信息，每条信息给出 $l,r,k_1,k_2,\dots,k_w$ ，表示 $a_{k_1},a_{k_2},\dots,a_{k_w}$ 严格大于 $[l,r]$ 中其他所有元素，构造一种方案或判断无解。

$1\leqslant n\leqslant 10^5,1\leqslant \sum w\leqslant 300000$

Solution：

所以说拓扑排序是一个边权为 $1$ 的差分约束？

既然是一个严格大于的关系，那就不难想到差分约束，发现边很多，但是 $\sum w$ 不是特别大，而且是一个区间问题，那就不难想到线段树优化连边，还要用到一个技巧就是对于每一个信息新建一个点这样就不用两两互相连了，把连边的代码写出来就会发现这题只要有环一定是负权环，那就可以不用 $SPFA$ 而是用拓扑排序求最长路，如果有点没进过队就无解。

对于已经给出的数字，就从原点向这个点连边权为这个数的边，这样跑最长路如果最后点的距离和这个数不相同的话就无解，因为最长路求的是一个下界，而这个最长路一定大于这条边的边权，下界都太大了那一定不合法。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n,s,m;

#define MAXN 100010

int p[MAXN],v[MAXN];

struct edge

{

	int to,nxt,v;

}e[MAXN + MAXN * 2 + MAXN * 3 * (1 + 17)];

int edgenum = 0;

int lin[MAXN * 2 + MAXN * 3] = {0};

int ind[MAXN * 2 + MAXN * 3];

void addedge(int a,int b,int c)

{

	++ind[b];

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

struct node

{

	int lc,rc;

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	if(l == r)

	{

		rt = l;

		return;

	}

	rt = newnode();

	build(t[rt].lc,l,mid);

	addedge(t[rt].lc,rt,0);

	build(t[rt].rc,mid + 1,r);

	addedge(t[rt].rc,rt,0);

	return;

}

void add(int rt,int L,int R,int st,int l,int r)

{

	if(L > R)return;

	if(L <= l && r <= R)

	{

		addedge(rt,st,0);

		return;

	}

	if(L <= mid)add(t[rt].lc,L,R,st,l,mid);

	if(R > mid)add(t[rt].rc,L,R,st,mid + 1,r);

	return;

}

int f[MAXN * 2 + MAXN * 3];

bool vis[MAXN];

int main()

{

	scanf("%d%d%d",&n,&s,&m);

	for(int i = 1;i <= s;++i)

	{

		scanf("%d%d",&p[i],&v[i]);

		addedge(0,p[i],v[i]);

		vis[p[i]] = true;

	}

	for(int i = 1;i <= n;++i)

	{

		if(!vis[i])addedge(0,i,1);

	}

	ptr = n;

	build(root,1,n);

	int l,r,k,w;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&l,&r,&w);

		int cur = ++ptr;

		int last = l;

		while(w--)

		{

			scanf("%d",&k);

			add(root,last,k - 1,cur,1,n);

			last = k + 1;

			addedge(cur,k,1);

		}

		add(root,last,r,cur,1,n);

	}

	memset(f,0xc0,sizeof(f));

	queue<int> q;q.push(0);f[0] = 0;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			--ind[e[i].to];

			f[e[i].to] = max(f[e[i].to],f[k] + e[i].v);

			if(ind[e[i].to] == 0)q.push(e[i].to);

		}

	}

	for(int i = 1;i <= ptr;++i)

	{

		if(f[i] < 0 || f[i] > 1000000000)

		{

			puts("NIE");

			return 0;

		}

	}

	for(int i = 1;i <= s;++i)

	{

		if(f[p[i]] != v[i])

		{

			puts("NIE");

			return 0;

		}

	}

	puts("TAK");

	for(int i = 1;i <= n;++i)printf("%d ",f[i]);

	puts("");

	return 0;

}