#P3588. [POI2015] PUS

    ID: 2639 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>2015线段树POISpecial Judge记忆化搜索拓扑排序

[POI2015] PUS

题目描述

给定一个长度为 nn 的正整数序列 aa,每个数都在 1110910^9 范围内,告诉你其中 ss 个数,并给出 mm 条信息,每条信息包含三个数 l,r,kl,r,k 以及接下来 kk 个正整数,表示 al,al+1,,ar1,ara_l, a_{l+1}, \ldots, a_{r-1}, a_r 里这 kk 个数中的任意一个都比任意一个剩下的 rl+1kr-l+1-k 个数大(严格大于,即没有等号)。

请任意构造出一组满足条件的方案,或者判断无解。

输入格式

第一行包含三个正整数 n,s,mn,s,m1sn1051 \leq s \leq n \leq 10^51m2×1051 \leq m \leq 2 \times 10^5)。接下来 ss 行,每行包含两个正整数 pi,dip_i,d_i,表示已知 api=dia_{p_i}=d_i,保证 pip_i 递增。

接下来 mm 行,每行一开始为三个正整数 li,ri,kil_i,r_i,k_i1li<rin1 \leq l_i < r_i \leq n1kirili1 \leq k_i \leq r_i-l_i),接下来 kik_i 个正整数 x1..x2...xkix_1..x_2...x_{k_i}lix1<x2<...<xkiril_i \leq x_1 < x_2 < ... < x_{k_i} \leq r_i),表示这 kik_i 个数中的任意一个都比任意一个剩下的 rili+1kir_i-l_i+1-k_i 个数大。(k3×105\sum k \leq 3 \times 10^5

输出格式

若无解,则输出 NIE。否则第一行输出 TAK,第二行输出 nn 个正整数,依次输出序列 aa 中每个数。

5 2 2
2 7
5 3
1 4 2 2 3
4 5 1 4
TAK
6 7 1000000000 6 3
3 2 1
2 3
3 5
1 3 1 2

NIE

2 1 1
1 1000000000
1 2 1 2
NIE

提示

原题名称:Pustynia。

本题另外提供两组额外样例,可以在附件中下载。