#P8299. [COCI 2012/2013 #2] INFORMACIJE

    ID: 9325 远端评测题 1000ms 32MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>图论2012Special JudgeCOCI(克罗地亚)

[COCI 2012/2013 #2] INFORMACIJE

题目背景

本题分值按 COCI 原题设置,满分 140140

题目描述

Mirko 很无聊,所以他拿起一张纸,写下了一个含有 NN 个元素的序列 AA1N1\sim N 的所有正整数在其中恰好仅出现一次。然后,他拿了另外一张纸,写下了 MM 个关于 AA 的描述。

每个描述有两种方式:

  • 1 x y v:表示 [x,y][x,y] 区间中最大的数为 vv

  • 2 x y v:表示 [x,y][x,y] 区间中最小的数为 vv

随后 Slavko 来偷走了他的第一张纸。Mirko 感到绝望,他想要你找到满足这些描述的序列,不需要跟原序列完全相同。

输入格式

第一行两个整数 N,M (1N200,0M4×104)N,M\ (1\le N\le 200, 0\le M\le 4\times 10^4),分别表示序列长度以及描述的数量。

接下来 MM 行每行一个描述。

输出格式

输出仅一行,一个满足所有描述的长为 NN 的序列,并且 1N1\sim N 在其中出现并仅出现一次,用空格隔开。如无解,输出 1-1

3 2
1 1 1 1
2 2 2 2
1 2 3
4 2
1 1 1 1
2 3 4 1
-1
5 2
1 2 3 3
2 4 5 4

1 2 3 4 5