Dòng thời gian hợp lệ (Valid Timeline)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $n$ cột mốc được đánh số từ $1$ đến $n$. Cột mốc thứ $i$ xảy ra vào năm $y_i$.

Ngoài ra, có $m$ quan hệ thứ tự. Mỗi quan hệ $u \rightarrow v$ có nghĩa là cột mốc $u$ bắt buộc phải được trình bày trước cột mốc $v$.

Hãy tìm một hoán vị

$$p_1,p_2,\ldots,p_n$$

của các số từ $1$ đến $n$ sao cho đồng thời thỏa mãn:

• Các cột mốc được trình bày theo thứ tự năm không giảm:

$$y_{p_1} \le y_{p_2} \le \cdots \le y_{p_n}.$$

• Với mọi quan hệ $u \rightarrow v$, cột mốc $u$ xuất hiện trước cột mốc $v$ trong hoán vị.

Nếu có nhiều thứ tự hợp lệ, hãy chọn hoán vị nhỏ nhất theo thứ tự từ điển của dãy chỉ số.

Hai hoán vị $p$ và $q$ được so sánh theo thứ tự từ điển như sau: tại vị trí đầu tiên $k$ mà $p_k \ne q_k$, hoán vị $p$ nhỏ hơn $q$ nếu $p_k < q_k$.

Nếu không tồn tại thứ tự nào thỏa mãn tất cả các yêu cầu, hãy in ra IMPOSSIBLE.

Input

• Dòng đầu tiên chứa hai số nguyên $n$ và $m$ — số lượng cột mốc và số lượng quan hệ thứ tự.
• Dòng thứ hai chứa $n$ số nguyên $y_1,y_2,\ldots,y_n$, trong đó $y_i$ là năm xảy ra của cột mốc thứ $i$.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$ và $v$, biểu diễn quan hệ $u \rightarrow v$: cột mốc $u$ phải được trình bày trước cột mốc $v$.

Output

Nếu tồn tại thứ tự hợp lệ, in ra $n$ chỉ số

$$p_1,p_2,\ldots,p_n$$

tạo thành hoán vị nhỏ nhất theo thứ tự từ điển trong tất cả các hoán vị thỏa mãn yêu cầu.

Nếu không tồn tại thứ tự hợp lệ, in ra:

IMPOSSIBLE

Subtask

Trong tất cả các Subtask: $1 \le n \le 2\cdot10^5$; $0 \le m \le 2\cdot10^5$; $1800 \le y_i \le 3000$; $1 \le u,v \le n$.

• Subtask 1 — 30%: $1 \le n \le 20$.
• Subtask 2 — 30%: $m=0$.
• Subtask 3 — 40%: $1 \le n \le 2\cdot10^5$; $0 \le m \le 2\cdot10^5$; $1800 \le y_i \le 3000$; $1 \le u,v \le n$.

Ví dụ

Ví dụ 1

Input

5 4
1950 1959 1974 1980 1997
1 2
2 3
2 4
4 5

Output

1 2 3 4 5

Giải thích

Các cột mốc có năm lần lượt là $1950,1959,1974,1980,1997$, nên thứ tự 1 2 3 4 5 có các năm không giảm.

Các quan hệ cũng đều được thỏa mãn: $1$ đứng trước $2$, $2$ đứng trước $3$ và $4$, còn $4$ đứng trước $5$.

Sau cột mốc $2$, cả cột mốc $3$ và $4$ đều không vi phạm các quan hệ đã cho. Tuy nhiên, cột mốc $3$ xảy ra vào năm $1974$, sớm hơn năm $1980$ của cột mốc $4$, nên $3$ phải đứng trước $4$.

Ví dụ 2

Input

3 0
2000 1990 1990

Output

2 3 1

Giải thích

Không có quan hệ thứ tự nào giữa các cột mốc.

Cột mốc $2$ và $3$ đều xảy ra vào năm $1990$, còn cột mốc $1$ xảy ra vào năm $2000$, vì vậy $2$ và $3$ phải đứng trước $1$.

Giữa hai cột mốc cùng năm $2$ và $3$, thứ tự 2 3 nhỏ hơn theo thứ tự từ điển. Do đó kết quả là 2 3 1.

Ví dụ 3

Input

3 3
1950 1960 1970
1 2
2 3
3 1

Output

IMPOSSIBLE

Giải thích

Các quan hệ yêu cầu đồng thời:

• cột mốc $1$ đứng trước $2$;
• cột mốc $2$ đứng trước $3$;
• cột mốc $3$ đứng trước $1$.

Ba yêu cầu này tạo thành một vòng phụ thuộc $1 \rightarrow 2 \rightarrow 3 \rightarrow 1$, nên không thể sắp xếp ba cột mốc thành một thứ tự thỏa mãn tất cả các quan hệ.

Vì vậy không tồn tại thứ tự hợp lệ.