I - Task Schedule and Priority Filter Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は、1 から N までの番号が付いた N 個のタスクを一列に並べて、スケジュール（1 から N の順列）を作ろうとしています。

M 件の依頼が、1 件ずつ順番に届きます。

依頼 j は、優先度 W_j と、タスクの順序制約 P_{j,1}, P_{j,2}, \ldots, P_{j,K_j} からなります。

高橋君がスケジュールにおいて依頼 j を守るとは、すべての i = 1, 2, \ldots, K_j - 1 について、タスク P_{j,i} がタスク P_{j,i+1} より前に現れることを意味します。

すなわち、スケジュール上で P_{j,1}, P_{j,2}, \ldots, P_{j,K_j} がこの相対順序で出現しなければなりません（連続している必要はありません）。

依頼は一度届くと、その後も残り続けます。

すなわち、t 件目の依頼が届いた直後には、依頼 1, 2, \ldots, t のすべてが存在します。

高橋君は、その時点の依頼の集合に対してフィルタの強さ X（非負整数）を選ぶことができます。

強さ X のフィルタを適用すると、優先度が X 以下の依頼（W_j \leq X）は無視でき、優先度が X より大きい依頼（W_j > X）はすべて同時に守らなければなりません。

X を大きくするほど無視できる依頼が増えるため、条件を満たすスケジュールが存在しやすくなります。

特に、X をすべての依頼の優先度の最大値以上にすれば、すべての依頼が無視されるため、任意の順列が条件を満たします。したがって、条件を満たす X は必ず存在します。

各 t = 1, 2, \ldots, M について、依頼 1, 2, \ldots, t だけを考えたとき、W_j > X であるすべての依頼 j を同時に守るスケジュールが存在するような最小の非負整数 X を X_t とします。

なお、各時点でスケジュールは自由に選び直してよく、また X の値も時点ごとに独立に決められます。

すべての X_t を求めてください。

さらに、すべての依頼 1, 2, \ldots, M が届いた後について、フィルタの強さ X_M で条件を満たすスケジュールを 1 つ出力してください。

制約

  • 2 \leq N \leq 2000
  • 1 \leq M \leq 1000
  • 1 \leq W_j \leq 10^9
  • 2 \leq K_j \leq N
  • \displaystyle\sum_{j=1}^{M} K_j \leq 3000
  • 1 \leq P_{j,i} \leq N
  • 各依頼 j の中で、P_{j,1}, P_{j,2}, \ldots, P_{j,K_j} はすべて異なる。ただし、異なる依頼の間では同じタスク番号が現れてもよい。
  • 入力はすべて整数である。

入力

N M
W_1 K_1 P_{1,1} P_{1,2} \ldots P_{1,K_1}
W_2 K_2 P_{2,1} P_{2,2} \ldots P_{2,K_2}
\vdots
W_M K_M P_{M,1} P_{M,2} \ldots P_{M,K_M}
  • 1 行目には、タスクの数 N と依頼の数 M がスペース区切りで与えられる。
  • j + 1 行目 (1 \leq j \leq M) には、依頼 j の情報が与えられる。
  • W_j は依頼 j の優先度である。
  • K_j は依頼 j に含まれるタスクの個数である。
  • P_{j,1}, P_{j,2}, \ldots, P_{j,K_j} は、依頼 j で指定された順序制約のタスク番号列である。

出力

2 行出力してください。

X_1 X_2 \ldots X_M
Q_1 Q_2 \ldots Q_N
  • 1 行目には、各 t = 1, 2, \ldots, M に対する最小値 X_t をスペース区切りで出力してください。
  • 2 行目には、すべての依頼が届いた後にフィルタの強さ X_M で条件を満たすスケジュール Q_1, Q_2, \ldots, Q_N をスペース区切りで出力してください。

Q_1, Q_2, \ldots, Q_N は 1 から N までの整数をちょうど 1 回ずつ含む順列でなければなりません。

W_j > X_M であるすべての依頼 j について、Q の中でタスク P_{j,1}, P_{j,2}, \ldots, P_{j,K_j} がこの相対順序で現れなければなりません（連続している必要はありません）。

条件を満たすスケジュールが複数ある場合は、どれを出力しても構いません。

入力例 1

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

出力例 1

0 0 3
3 4 1 2

入力例 2

3 4
10 2 1 2
20 2 2 3
15 2 3 1
5 2 3 2

出力例 2

0 0 10 10
2 3 1

入力例 3

8 8
50 3 1 3 5
20 2 2 4
70 4 5 6 7 8
40 3 4 1 2
60 2 8 3
10 5 2 5 7 1 6
30 3 6 4 3
80 4 3 2 8 1

出力例 3

0 0 0 20 50 50 50 60
3 4 5 2 6 7 8 1

入力例 4

15 15
100 5 1 2 3 4 5
250 4 6 7 8 9
150 3 10 11 12
300 6 5 10 15 14 13 1
50 2 9 6
400 5 2 7 12 3 8
120 4 11 4 14 6
500 7 15 1 8 2 13 9 5
80 3 3 10 7
350 5 4 6 8 10 12
220 6 13 11 9 7 5 3
180 2 14 2
600 8 1 4 7 10 13 15 12 9
90 4 8 5 2 11
450 6 6 1 12 14 3 15

出力例 4

0 0 0 100 100 100 100 400 400 400 400 400 500 500 500
1 2 3 5 6 8 11 14 4 7 10 13 15 12 9

入力例 5

2 1
1000000000 2 2 1

出力例 5

0
2 1

Score : 400 pts

Problem Statement

Takahashi is trying to arrange N tasks, numbered from 1 to N, in a row to create a schedule (a permutation of 1 to N).

M requests arrive one by one in order. Request j consists of a priority W_j and a task ordering constraint P_{j,1}, P_{j,2}, \ldots, P_{j,K_j}.

For Takahashi to satisfy request j in a schedule means that for all i = 1, 2, \ldots, K_j - 1, task P_{j,i} appears before task P_{j,i+1} in the schedule. In other words, P_{j,1}, P_{j,2}, \ldots, P_{j,K_j} must appear in this relative order in the schedule (they do not need to be consecutive).

Once a request arrives, it remains thereafter. That is, immediately after the t-th request arrives, all requests 1, 2, \ldots, t are present.

Takahashi can choose a filter strength X (a non-negative integer) for the current set of requests. When a filter of strength X is applied, requests with priority at most X (W_j \leq X) can be ignored, while all requests with priority greater than X (W_j > X) must be satisfied simultaneously.

The larger X is, the more requests can be ignored, making it easier for a valid schedule to exist. In particular, if X is at least the maximum priority among all requests, then all requests are ignored and any permutation satisfies the condition. Therefore, a valid X always exists.

For each t = 1, 2, \ldots, M, considering only requests 1, 2, \ldots, t, let X_t be the minimum non-negative integer X such that there exists a schedule that simultaneously satisfies all requests j with W_j > X.

Note that the schedule may be freely re-chosen at each time step, and the value of X is also determined independently at each time step.

Find all X_t. Additionally, after all requests 1, 2, \ldots, M have arrived, output one schedule that satisfies the condition with filter strength X_M.

Constraints

  • 2 \leq N \leq 2000
  • 1 \leq M \leq 1000
  • 1 \leq W_j \leq 10^9
  • 2 \leq K_j \leq N
  • \displaystyle\sum_{j=1}^{M} K_j \leq 3000
  • 1 \leq P_{j,i} \leq N
  • Within each request j, the values P_{j,1}, P_{j,2}, \ldots, P_{j,K_j} are all distinct. However, the same task number may appear across different requests.
  • All input values are integers.

Input

N M
W_1 K_1 P_{1,1} P_{1,2} \ldots P_{1,K_1}
W_2 K_2 P_{2,1} P_{2,2} \ldots P_{2,K_2}
\vdots
W_M K_M P_{M,1} P_{M,2} \ldots P_{M,K_M}
  • The first line contains the number of tasks N and the number of requests M, separated by a space.
  • The (j + 1)-th line (1 \leq j \leq M) contains the information for request j.
  • W_j is the priority of request j.
  • K_j is the number of tasks included in request j.
  • P_{j,1}, P_{j,2}, \ldots, P_{j,K_j} is the sequence of task numbers specifying the ordering constraint of request j.

Output

Output 2 lines.

X_1 X_2 \ldots X_M
Q_1 Q_2 \ldots Q_N
  • On the first line, output the minimum values X_t for each t = 1, 2, \ldots, M, separated by spaces.
  • On the second line, output a schedule Q_1, Q_2, \ldots, Q_N that satisfies the condition with filter strength X_M after all requests have arrived, separated by spaces.

Q_1, Q_2, \ldots, Q_N must be a permutation containing each integer from 1 to N exactly once. For every request j with W_j > X_M, the tasks P_{j,1}, P_{j,2}, \ldots, P_{j,K_j} must appear in this relative order in Q (they do not need to be consecutive).

If there are multiple valid schedules, you may output any of them.

Sample Input 1

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

Sample Output 1

0 0 3
3 4 1 2

Sample Input 2

3 4
10 2 1 2
20 2 2 3
15 2 3 1
5 2 3 2

Sample Output 2

0 0 10 10
2 3 1

Sample Input 3

8 8
50 3 1 3 5
20 2 2 4
70 4 5 6 7 8
40 3 4 1 2
60 2 8 3
10 5 2 5 7 1 6
30 3 6 4 3
80 4 3 2 8 1

Sample Output 3

0 0 0 20 50 50 50 60
3 4 5 2 6 7 8 1

Sample Input 4

15 15
100 5 1 2 3 4 5
250 4 6 7 8 9
150 3 10 11 12
300 6 5 10 15 14 13 1
50 2 9 6
400 5 2 7 12 3 8
120 4 11 4 14 6
500 7 15 1 8 2 13 9 5
80 3 3 10 7
350 5 4 6 8 10 12
220 6 13 11 9 7 5 3
180 2 14 2
600 8 1 4 7 10 13 15 12 9
90 4 8 5 2 11
450 6 6 1 12 14 3 15

Sample Output 4

0 0 0 100 100 100 100 400 400 400 400 400 500 500 500
1 2 3 5 6 8 11 14 4 7 10 13 15 12 9

Sample Input 5

2 1
1000000000 2 2 1

Sample Output 5

0
2 1