[COCI 2012/2013 #2] INFORMACIJE

Luogu

IDLGP8299

Time1000ms

Memory32MB

DifficultyP5

图论2012Special JudgeCOCI（克罗地亚）

Mirko 很无聊，所以他拿起一张纸，写下了一个含有 $N$ 个元素的序列 $A$，$1\sim N$ 的所有正整数在其中恰好仅出现一次。然后，他拿了另外一张纸，写下了 $M$ 个关于 $A$ 的描述。每个描述有两种方式： - `1 x y v`：表示 $[x,y]$ 区间中最大的数为 $v$。 - `2 x y v`：表示 $[x,y]$ 区间中最小的数为 $v$。随后 Slavko 来偷走了他的第一张纸。Mirko 感到绝望，他想要你找到满足这些描述的序列，不需要跟原序列完全相同。 ## Input 第一行两个整数 $N,M\ (1\le N\le 200, 0\le M\le 4\times 10^4)$，分别表示序列长度以及描述的数量。接下来 $M$ 行每行一个描述。 ## Output 输出仅一行，一个满足所有描述的长为 $N$ 的序列，并且 $1\sim N$ 在其中出现并仅出现一次，用空格隔开。如无解，输出 $-1$。 [samples] ## Background **本题分值按 COCI 原题设置，满分 $140$。**

Samples

Input #1

3 2
1 1 1 1
2 2 2 2

Output #1

1 2 3

Input #2

4 2
1 1 1 1
2 3 4 1

Output #2

-1

Input #3

5 2
1 2 3 3
2 4 5 4

Output #3

1 2 3 4 5

API Response (JSON)

{
  "problem": {
    "name": "[COCI 2012/2013 #2] INFORMACIJE",
    "description": {
      "content": "Mirko 很无聊，所以他拿起一张纸，写下了一个含有 $N$ 个元素的序列 $A$，$1\\sim N$ 的所有正整数在其中恰好仅出现一次。然后，他拿了另外一张纸，写下了 $M$ 个关于 $A$ 的描述。 每个描述有两种方式： - `1 x y v`：表示 $[x,y]$ 区间中最大的数为 $v$。 - `2 x y v`：表示 $[x,y]$ 区间中最小的数为 $v$。 随后 Slavko",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 32768
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8299"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Mirko 很无聊，所以他拿起一张纸，写下了一个含有 $N$ 个元素的序列 $A$，$1\\sim N$ 的所有正整数在其中恰好仅出现一次。然后，他拿了另外一张纸，写下了 $M$ 个关于 $A$ 的描述。\n\n每个描述有两种方式：\n\n- `1 x y v`：表示 $[x,y]$ 区间中最大的数为 $v$。\n\n- `2 x y v`：表示 $[x,y]$ 区间中最小的数为 $v$。\n\n随后 Slavko...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments