Hospital Queue

题意翻译

有 $ n $ 个病人来排队看病，一种合法的排队方案需要满足以下条件： 一、${\forall}$ $ 1 $ ${\leq}$ $ i $ ${\leq}$ $ n $，编号为 $ i $ 的病人必须排在前 $ p_i $ 位。 二、${\forall}$ $ 1 $ ${\leq}$ $ i $ ${\leq}$ $ m $，编号为 $ a_i $ 的病人必须排在编号为 $ b_i $ 的病人前面。 你需要对于每一位病人，求出在所有合法的排队方案中，他能排在的最靠前的位置。 **数据保证一定存在合法的排队方案。** 保证 $ 1 $ ${\leq}$ $ n $ ${\leq}$ $ 2000 $；$ 0 $ ${\leq}$ $ m $ ${\leq}$ $ 2000 $

题目描述

There are $ n $ people (numbered from $ 1 $ to $ n $ ) signed up for a doctor's appointment. The doctor has to choose in which order he will appoint these people. The $ i $ -th patient should be appointed among the first $ p_i $ people. There are also $ m $ restrictions of the following format: the $ i $ -th restriction is denoted by two integers $ (a_i, b_i) $ and means that the patient with the index $ a_i $ should be appointed earlier than the patient with the index $ b_i $ . For example, if $ n = 4 $ , $ p = [2, 3, 2, 4] $ , $ m = 1 $ , $ a = [3] $ and $ b = [1] $ , then the only order of appointment of patients that does not violate the restrictions is $ [3, 1, 2, 4] $ . For $ n =3 $ , $ p = [3, 3, 3] $ , $ m = 0 $ , $ a = [] $ and $ b = [] $ , any order of appointment is valid. For each patient, calculate the minimum position in the order that they can have among all possible orderings that don't violate the restrictions.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1 \le n \le 2000 $ ; $ 0 \le m \le 2000 $ ). The second line contains $ n $ integers $ p_1, p_2, \dots, p_n $ ( $ 1 \le p_i \le n $ ). Then $ m $ lines follow. The $ i $ -th of them contains two integers $ a_i $ and $ b_i $ ( $ 1 \le a_i, b_i \le n $ ; $ a_i \ne b_i $ ). All pairs of $ (a_i, b_i) $ are distinct (i. e. if $ i \ne j $ , then either $ a_i \ne a_j $ , $ b_i \ne b_j $ , or both). Additional constraint on the input: there is at least one valid order of patients.

输出格式

Print $ n $ integers, where $ i $ -th integer is equal to the minimum position of $ i $ -th patient in the order, among all valid orders. Positions in the order are numbered from $ 1 $ to $ n $ .

输入输出样例

输入样例 #1

4 1
2 3 2 4
3 1

输出样例 #1

2 3 1 4

输入样例 #2

3 0
3 3 3

输出样例 #2

1 1 1

输入样例 #3

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

输出样例 #3

4 2 1 1 5

说明

In the first example, $ [3, 1, 2, 4] $ the only one valid order, so the minimum position of each patient is equal to their position in this order. In the second example, any order is valid, so any patient can be appointed first. In the third example, there are three valid orders: $ [4, 2, 3, 1, 5] $ , $ [3, 4, 2, 1, 5] $ and $ [4, 3, 2, 1, 5] $ .

**医院排队**

**题意翻译**

有 $ n $ 个病人来排队看病，一种合法的排队方案需要满足以下条件：

一、对于所有 $ 1 \leq i \leq n $，编号为 $ i $ 的病人必须排在前 $ p_i $ 位。

二、对于所有 $ 1 \leq i \leq m $，编号为 $ a_i $ 的病人必须排在编号为 $ b_i $ 的病人前面。

你需要对于每一位病人，求出在所有合法的排队方案中，他能排在的最靠前的位置。

**数据保证一定存在合法的排队方案。**

保证 $ 1 \leq n \leq 2000 $；$ 0 \leq m \leq 2000 $

**题目描述**

有 $ n $ 个人（编号从 $ 1 $ 到 $ n $）报名看医生。医生必须选择他们的预约顺序。第 $ i $ 个病人应该在最先的 $ p_i $ 人中被预约。还有 $ m $ 个限制，格式如下：第 $ i $ 个限制由两个整数 $ (a_i, b_i) $ 表示，意味着编号为 $ a_i $ 的病人应该比编号为 $ b_i $ 的病人更早被预约。

例如，如果 $ n = 4 $，$ p = [2, 3, 2, 4] $，$ m = 1 $，$ a = [3] $ 和 $ b = [1] $，那么唯一不违反限制的预约顺序是 $ [3, 1, 2, 4] $。对于 $ n = 3 $，$ p = [3, 3, 3] $，$ m = 0 $，$ a = [] $ 和 $ b = [] $，任何预约顺序都是有效的。

对于每个病人，计算在所有可能的、不违反限制的预约顺序中，他们能占据的最小位置。

**输入输出格式**

**输入格式**

第一行包含两个整数 $ n $ 和 $ m $（$ 1 \leq n \leq 2000 $；$ 0 \leq m \leq 2000 $）。

第二行包含 $ n $ 个整数 $ p_1, p_2, \dots, p_n $（$ 1 \leq p_i \leq n $）。

接下来 $ m $ 行，每行包含两个整数 $ a_i $ 和 $ b_i $（$ 1 \leq a_i, b_i \leq n $；$ a_i \neq b_i $）。所有 $ (a_i, b_i) $ 对都是唯一的（即如果 $ i \neq j $，那么 $ a_i \neq a_j $ 或 $ b_i \neq b_j $ 或两者都不相等）。

输入的附加限制：至少存在一个有效的病人顺序。

**输出格式**

输出 $ n $ 个整数，其中第 $ i $ 个整数表示在所有有效的顺序中，第 $ i $ 个病人的最小位置。顺序中的位置从 $ 1 $ 编号到 $ n $。

**输入输出样例**

**输入样例 #1**
```
4 1
2 3 2 4
3 1
```
**输出样例 #1**
```
2 3 1 4
```

**输入样例 #2**
```
3 0
3 3 3
```
**输出样例 #2**
```
1 1 1
```

**输入样例 #3**
```
5 3
4 3 3 2 5
3 1
1 5
4 2
```
**输出样例 #3**
```
4 2 1 1 5
```

**说明**

在第一个例子中，$ [3, 1, 2, 4] $ 是唯一有效的顺序，所以每个病人的最小位置等于他们在该顺序中的位置。

在第二个例子中，任何顺序都是有效的，所以任何病人都可以首先被预约。

在第三个例子中，有三个有效的顺序：$ [4, 2, 3, 1, 5] $，$ [3, 4, 2, 1, 5] $ 和 $ [4, 3, 2, 1, 5] $。**医院排队** **题意翻译** 有 $ n $ 个病人来排队看病，一种合法的排队方案需要满足以下条件： 一、对于所有 $ 1 \leq i \leq n $，编号为 $ i $ 的病人必须排在前 $ p_i $ 位。 二、对于所有 $ 1 \leq i \leq m $，编号为 $ a_i $ 的病人必须排在编号为 $ b_i $ 的病人前面。 你需要对于每一位病人，求出在所有合法的排队方案中，他能排在的最靠前的位置。 **数据保证一定存在合法的排队方案。** 保证 $ 1 \leq n \leq 2000 $；$ 0 \leq m \leq 2000 $ **题目描述** 有 $ n $ 个人（编号从 $ 1 $ 到 $ n $）报名看医生。医生必须选择他们的预约顺序。第 $ i $ 个病人应该在最先的 $ p_i $ 人中被预约。还有 $ m $ 个限制，格式如下：第 $ i $ 个限制由两个整数 $ (a_i, b_i) $ 表示，意味着编号为 $ a_i $ 的病人应该比编号为 $ b_i $ 的病人更早被预约。 例如，如果 $ n = 4 $，$ p = [2, 3, 2, 4] $，$ m = 1 $，$ a = [3] $ 和 $ b = [1] $，那么唯一不违反限制的预约顺序是 $ [3, 1, 2, 4] $。对于 $ n = 3 $，$ p = [3, 3, 3] $，$ m = 0 $，$ a = [] $ 和 $ b = [] $，任何预约顺序都是有效的。 对于每个病人，计算在所有可能的、不违反限制的预约顺序中，他们能占据的最小位置。 **输入输出格式** **输入格式** 第一行包含两个整数 $ n $ 和 $ m $（$ 1 \leq n \leq 2000 $；$ 0 \leq m \leq 2000 $）。 第二行包含 $ n $ 个整数 $ p_1, p_2, \dots, p_n $（$ 1 \leq p_i \leq n $）。 接下来 $ m $ 行，每行包含两个整数 $ a_i $ 和 $ b_i $（$ 1 \leq a_i, b_i \leq n $；$ a_i \neq b_i $）。所有 $ (a_i, b_i) $ 对都是唯一的（即如果 $ i \neq j $，那么 $ a_i \neq a_j $ 或 $ b_i \neq b_j $ 或两者都不相等）。 输入的附加限制：至少存在一个有效的病人顺序。 **输出格式** 输出 $ n $ 个整数，其中第 $ i $ 个整数表示在所有有效的顺序中，第 $ i $ 个病人的最小位置。顺序中的位置从 $ 1 $ 编号到 $ n $。 **输入输出样例** **输入样例 #1** ``` 4 1 2 3 2 4 3 1 ``` **输出样例 #1** ``` 2 3 1 4 ``` **输入样例 #2** ``` 3 0 3 3 3 ``` **输出样例 #2** ``` 1 1 1 ``` **输入样例 #3** ``` 5 3 4 3 3 2 5 3 1 1 5 4 2 ``` **输出样例 #3** ``` 4 2 1 1 5 ``` **说明** 在第一个例子中，$ [3, 1, 2, 4] $ 是唯一有效的顺序，所以每个病人的最小位置等于他们在该顺序中的位置。 在第二个例子中，任何顺序都是有效的，所以任何病人都可以首先被预约。 在第三个例子中，有三个有效的顺序：$ [4, 2, 3, 1, 5] $，$ [3, 4, 2, 1, 5] $ 和 $ [4, 3, 2, 1, 5] $。