# Coding Challenge #4

## Đề Bài

:::spoiler [Đề bài gốc](https://oj.vnoi.info/problem/coding_challenge_coin) có thể được đọc trên hệ thống [VNOJ](https://oj.vnoi.info/contest/coding_challenge_4)
# **Coding Challenge #4 - Cân xu**

Bổn Sâm có $n$ đồng xu **khác nhau về trọng lượng** và một cái cân hai bên. Mỗi khi anh ta đặt đồng xu $x$ và $y$ lên cân, trọng lượng tương đối giữa chúng sẽ được hiển thị - tức là anh ta biết được giữa $x$ và $y$, đồng nào nặng hơn.

Gọi **cấp bậc** của đồng xu $x$ là số lượng đồng xu *không nặng hơn* đồng xu $x$ (bao gồm cả chính nó). Do đó, đồng xu nhẹ nhất có cấp bậc là $1$, đồng nhẹ nhì là $2$, ..., và đồng nặng nhất có cấp bậc là $n$.

Sẽ có $m$ lần cân. Với mỗi đồng xu, hãy xác định sau **lần cân thứ** $m$ thì có thể chắc chắn biết cấp bậc của đồng xu đó.

## Input

Dòng đầu tiên nhập hai số nguyên $n$, $m$.

Tiếp theo là $m$ dòng, dòng thứ $i$ nhập hai số nguyên $x$, $y$, cho biết kết quả lần cân thứ $i$ là **đồng xu $x$ nặng hơn đồng xu $y$**.

Đảm bảo rằng các kết quả cân **không mâu thuẫn** với nhau.

## Output

In ra một dòng gồm $n$ số nguyên.

Số thứ $i$ là **lần cân sớm nhất** sau đó có thể xác định chắc chắn **cấp bậc của đồng xu $i$**.

Nếu **không thể xác định**, in `–1` tại vị trí đó.

## Scoring

### Giới hạn dữ liệu

- $2 \leq n \leq 200,000$
- $1 \leq m \leq 800,000$
- $1 \leq x, y \leq n$, $x \neq y$

### Subtask

- Subtask $1$ ($6$ điểm): $n \leq 7$, $m \leq 20$
- Subtask $2$ ($16$ điểm): $n \leq 100$, $m \leq 400$
- Subtask $3$ ($10$ điểm): $n \leq 1000$, $m \leq 4000$
- Subtask $4$ ($68$ điểm): không có ràng buộc gì thêm

### Lưu ý

Trong mỗi subtask, nếu bạn **chỉ xác định đúng rằng cấp bậc của từng đồng xu có thể hay không thể được xác định**, nhưng **không xác định đúng là được xác định sau lần cân thứ mấy**, bạn vẫn sẽ nhận được **$50$% số điểm** của subtask đó.

## Sample

### Sample Input 1

4 4
2 4
3 1
4 1
2 3

### Sample Output 1

3 4 -1 -1

### Sample Input 2

6 8
1 5
5 4
6 2
2 5
4 3
6 1
6 5
2 1

### Sample Output 2

8 8 5 5 5 6

### Notes

#### Giải thích ví dụ $1$

Ta có thể xác định rằng sau $3$ lần cân đầu tiên, đồng xu $1$ là đồng xu nặng nhất, nhưng không thể biết điều đó chỉ sau $2$ lần cân. Do đó, số nguyên đầu tiên trong kết quả
đúng là $3$.
Tương tự, ta có thể xác định rằng đồng xu $2$ là đồng xu nhẹ nhất sau $4$ lần cân, nhưng không phải sau $3$ lần cân. Vì vậy, số nguyên thứ hai trong kết quả đúng là $4$.
Lưu ý rằng cả hai thứ tự $2, 4, 3, 1$ và $2, 3, 4, 1$ đều là các cách sắp xếp hợp lệ của trọng lượng các đồng xu. Do đó, đồng xu $3$ có thể có cấp bậc $2$ hoặc $3$, đều phù hợp với tất cả các kết quả cân, vì vậy cấp bậc của đồng xu $3$ không bao giờ được xác định chắc chắn. Tương tự, đồng xu $4$ cũng không bao giờ có cấp bậc xác định.
Nếu kết quả của bạn là `1 1 -1 -1`, bạn sẽ đạt được $50\%$ số điểm cho test nhỏ này.

:::

## Lời Giải

### [Subtask 1](https://hackmd.io/_V4EhjBxT8aZfBSCMuNYmQ#Subtask-1)

**Giới hạn:** $n \leq 7$; $m \leq 20$

#### Ý Tưởng

- Đặt $P$ là thứ tự của các đồng xu được sắp xếp tăng dần theo cấp bậc của chúng.
Với định nghĩa này, ta có thể biểu diễn $P$ bằng một hoán vị của $n$ số tự nhiên đầu tiên.
:::spoiler Ví dụ
Với $n = 3$, $P = (2, 3, 1)$ có thể được hiểu như:
- Đồng xu $2$ có cấp bậc là $1$;
- Đồng xu $3$ có cấp bậc là $2$;
- Đồng xu $1$ có cấp bậc là $3$.
:::
- Đặt $e_i = (x_i, y_i)$ là cặp đồng xu được cân ở lần cân thứ $i$ ($1 \leq i \leq m$; đồng xu $x_i$ nặng hơn đồng xu $y_i$).
Đặt $E_j = \{e_i \vert 1 \leq i \leq j \}$ là tập hợp cặp đồng xu của $i$ lần cân đầu tiên.
- Ta gọi một thứ tự $P$ là hợp lệ với một tập hợp lần cân $E$ nếu không tồn tại một cặp đồng xu nào mà thứ tự của chúng không thỏa kết quả của một lần cân nào đó trong $E$.
Nói cách khác, nếu $(x, y) \in E$ thì vị trí của đồng xu $y$ phải nằm phía trước vị trí của đồng xu $x$ trong $P$ (đồng xu $x$ có cấp bậc cao hơn đồng xu $y$).
Vì dữ liệu đầu vào đảm bảo rằng các kết quả cân không mâu thuẫn với nhau, ít nhất một thứ tự hợp lệ phải tồn tại với tập hợp $m$ lần cân ($E_m$).
- Cấp bậc của đồng xu $z$ là có thể chắc chắn xác định được với tập hợp lần cân $E$ **nếu trong mọi thứ tự $P$ hợp lệ so với $E$, cấp bậc của $z$ không đổi** (tạm gọi đây là điều kiện $(1)$).
Vì vậy, nếu ta chỉ kiểm tra rằng cấp bậc của từng đồng xu có thể hay không thể được xác định (và đạt $50$% số điểm của [subtask 1](https://hackmd.io/_V4EhjBxT8aZfBSCMuNYmQ#Subtask-1)), ta có thể:
- Duyệt qua tất cả $n!$ hoán vị để tìm các thứ tự hợp lệ; và
- Với mỗi đồng xu, ta kiểm tra liệu có tồn tại hai thứ tự hợp lệ khác nhau mà cấp bậc của đồng xu trong hai thứ tự đó là khác nhau.
- Với mỗi đồng xu $z$, việc tìm được thời điểm sớm nhất mà có thể chắc chắn xác định cấp bậc của đồng xu đó sẽ tương đương với việc tìm ra tập hợp gồm các lần cân đầu tiên với kích thước nhỏ nhất sao cho điều kiện $(1)$ vẫn thỏa.
Nói cách khác, ta cần tìm $i$ nhỏ nhất sao cho với $E_i$, cấp bậc $z$ có thể chắc chắn xác định.
Để thực hiện điều này, ta có thể duyệt qua một tập hợp lần cân và thực hiện kiểm tra như trên.

#### Độ Phức Tạp

- Ý tưởng nêu trên có thể được cài đặt với độ phức tạp thời gian $O(m \cdot n! \cdot (m + n))$.
- Ta cần duyệt qua $O(m)$ tập hợp lần cân.
- Với mỗi tập hợp, ta cần duyệt qua $O(n!)$ hoán vị để tìm các thứ tự hợp lệ.
- Với mỗi thứ tự, ta thực hiện kiểm tra tính hợp lệ bằng cách duyệt qua $O(m)$ lần cân. Nếu thứ tự hợp lệ, chúng ta cần phải kiểm tra cấp bậc của $O(n)$ đồng xu có khác so với thứ tự hợp lệ khác không.

#### Code Minh Họa

:::spoiler Code C++ minh họa

#include <bits/stdc++.h>
using namespace std;

template<class A, class B> bool maximize(A &a, const B &b) { return (a < b) ? (a = b, true) : false; }
template<class A, class B> bool minimize(A &a, const B &b) { return (a > b) ? (a = b, true) : false; }

constexpr int MAX_N = 200'005, MAX_M = 800'005, INF = 0X3F3F3F3F, NINF = 0XC0C0C0C0;

int n, m, x[MAX_M], y[MAX_M];

void input() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> x[i] >> y[i];
        --x[i];
        --y[i];
    }
}

vector<int> findPositions(const vector<int> &permutation) {
    const int n = permutation.size();
    vector<int> positions(n);
    for (int i = 0; i < n; ++i)
        positions[permutation[i]] = i;
    return positions;
}

bool checkValid(const vector<int> &order, const int e) {
    const vector<int> &positions(findPositions(order));
    for (int i = 0; i < e; ++i)
        if (positions[x[i]] > positions[y[i]])
            return false;
    return true;
}

bool checkInvalid(const vector<int> &order, const int e) {
    return !checkValid(order, e);
}

vector<int> findLevels(const int e) {
    vector<int> levels(n, n), permutation(n);
    /**
        level = -1      :   The level cannot be determined
        level = n       :   The level has not been determined yet
                            (as there is no contradiction, there should no final result with this value)
        0 <= level < n  :   The level is currently determined
    **/

    iota(permutation.begin(), permutation.end(), 0);

    do {
        if (checkInvalid(permutation, e))
            continue;
        for (int i = 0; i < n; ++i) {
            const auto &value = permutation[i];
            auto &level = levels[value];
            if (level < 0)
                continue;
            if (level == n) {
                level = i;
                continue;
            }
            if (level != i)
                level = -1;
        }
    } while (next_permutation(permutation.begin(), permutation.end()));

    return levels;
}

vector<int> findWhen() {
    vector<int> result(n, -1);
    for (int e = 1, i = 0; e <= m; ++e) {
        const auto &levels(findLevels(e));
        for (i = 0; i < n; ++i) {
            if (result[i] >= 0 || levels[i] < 0)
                continue;
            result[i] = e;
        }
    }
    return result;
}

int main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();

    for (const int &e : findWhen())
        cout << e << ' ';
    cout << '\n';

    return 0;
}

:::

### [Subtask 2](https://hackmd.io/_V4EhjBxT8aZfBSCMuNYmQ#Subtask-2)

**Giới hạn:** $n \leq 100$; $m \leq 400$

#### Ý Tưởng

- Ta có thể biểu diễn mối quan hệ trọng lượng tương đối bằng cách dựng một đồ thị.
Cụ thể hơn, đặt $G = (V, E)$ với:
- $V$ là tập hợp các đồng xu
- $E$ là tập hợp các lần cân: $(x, y) \in E$ (tồn tại một cung trực tiếp từ $x$ tới $y$) nếu như tồn tại một lần cân xác định được rằng đồng xu $x$ nặng hơn đồng xu $y$.
- Ta nhận thấy rằng: đồng xu $x$ có thể được xác định nặng hơn đồng xu $y$ khi đồ thị $G$ phải chứa ít nhất một đường đi từ $x$ tới $y$.
:::spoiler Giải thích
- Giả sử đường đi từ $x$ tới $y$ là một dãy các đỉnh $U_1, ..., U_k$ (với $k \geq 2$, $U_1 = x$, $U_k = y$) thì theo cách ta dựng đồ thị, đồng xu $U_i$ phải nặng hơn đồng xu $U_{i + 1}$ (với $1 \leq i < k$). Vì thế, dựa vào tích chất bắc cầu, ta có đồng xu $U_1$ (hay $x$) phải nặng hơn đồng xu $U_k$ (hay $y$).
:::
- Tập hợp các đỉnh mà có thể **đến được từ đỉnh $x$** cũng đồng thời là tập hợp các đỉnh đại diện cho đồng xu có thể xác định **nhẹ** hơn đồng xu $x$.
- Ta có thể xác định được tập hợp này bằng cách sử dụng [các thuật toán duyệt đồ thị](https://en.wikipedia.org/wiki/Graph_traversal) như [BFS](https://en.wikipedia.org/wiki/Breadth-first_search) hoặc [DFS](https://en.wikipedia.org/wiki/Depth-first_search) trên đồ thị $G$.
- Tương tự, tập hợp các đỉnh mà có thể **đi tới được đỉnh $x$** cũng đồng thời là tập hợp các đỉnh đại diện cho đồng xu nhẹ có thể xác định **nặng** đồng xu $x$.
- Để xác định được tập hợp này, ta cũng có thể sử dụng [các thuật toán duyệt đồ thị](https://usaco.guide/silver/graph-traversal?lang=cpp) như trên nhưng trên [một đồ thị có chiều các cạnh được đảo so với $G$](https://en.wikipedia.org/wiki/Transpose_graph#:~:text=In%20the%20mathematical%20and%20algorithmic,the%20corresponding%20edges%20in%20G.).
- Cụ thể hơn, ta có thể đặt $G^T = (V, E^T)$ với $E^T = \{(y, x) \vert (x, y) \in E\}$
:::spoiler Minh họa đồ thị được dựng từ sample
- Đồ thị được dựng từ [sample $1$](https://hackmd.io/_V4EhjBxT8aZfBSCMuNYmQ?both#Sample-Input-1)
- Đồ thị được dựng từ [sample $2$](https://hackmd.io/_V4EhjBxT8aZfBSCMuNYmQ?both#Sample-Input-2)
:::
- Vì vậy, nếu ta chỉ muốn kiểm tra rằng cấp bậc của một đồng xu $z$ có thể hay không thể được xác định (và đạt $50$% số điểm của [subtask 2](https://hackmd.io/_V4EhjBxT8aZfBSCMuNYmQ#Subtask-2)), ta có thể thực hiện bằng cách kiểm tra **phép hợp của hai tập hợp đến được từ $z$ và có thể đi đến được $z$ có chứa mọi đỉnh của đồ thị đã cho không** (cấp bậc của đồng xu $z$ chỉ có thể xác định khi trong lượng tương đối giữa nó và các đồng xu khác đều có thể xác định). Tạm gọi điều kiện của việc kiểm tra này là điều kiện $(2)$.
- Tương tự như [subtask 1](https://hackmd.io/_V4EhjBxT8aZfBSCMuNYmQ#Subtask-1), với mỗi đồng xu $z$, việc tìm được thời điểm sớm nhất mà có thể chắc chắn xác định cấp bậc của đồng xu đó sẽ tương đương với việc tìm ra tập hợp gồm các lần cân đầu tiên với kích thước nhỏ nhất sao cho điều kiện $(2)$ vẫn thỏa.

#### Độ Phức Tạp

- Ý tưởng nêu trên có thể được cài đặt với độ phức tạp thời gian $O(n \cdot m \cdot (n + m))$.
- Ta cần duyệt qua $O(n)$ đỉnh đại diện cho các đồng xu.
- Với mỗi đỉnh, ta cần duyệt qua $O(m)$ tập hợp lần cân.
- Với mỗi tập hợp lần cân, việc duyệt đồ thị có thể được thể được hiện tại với thuật toán [BFS](html) hoặc [DFS](https://cp-algorithms.com/graph/depth-first-search.html) với độ phức tạp thời gian $O(n + m)$.

#### Code Minh Họa

:::spoiler Code C++ minh họa

#include <bits/stdc++.h>
using namespace std;

template<class A, class B> bool maximize(A &a, const B &b) { return (a < b) ? (a = b, true) : false; }
template<class A, class B> bool minimize(A &a, const B &b) { return (a > b) ? (a = b, true) : false; }

constexpr int MAX_N = 200'005, MAX_M = 800'005, INF = 0X3F3F3F3F, NINF = 0XC0C0C0C0;

vector<pair<int, int> > graph[MAX_N], reversedGraph[MAX_N];
int n, m, x[MAX_M], y[MAX_M];

void input() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> x[i] >> y[i];
        graph[x[i]].emplace_back(i, y[i]);
        reversedGraph[y[i]].emplace_back(i, x[i]);
    }
}

namespace ReachabilityChecker {

    bool visited[MAX_N];
    int limit;

    void runFirstDFS(const int x) {
        visited[x] = true;
        for (const auto &[e, y] : graph[x]) {
            if (visited[y] || e > limit)
                continue;
            runFirstDFS(y);
        }
    }

    void runSecondDFS(const int x) {
        visited[x] = true;
        for (const auto &[e, y] : reversedGraph[x]) {
            if (visited[y] || e > limit)
                continue;
            runSecondDFS(y);
        }
    }

    int check(const int source) {
        for (int i = 1; i <= n; ++i)
            visited[i] = false;
        runFirstDFS(source);
        runSecondDFS(source);
        for (int i = 1; i <= n; ++i)
            if (!visited[i])
                return false;
        return true;
    }

}

void determineWhen() {
    vector<int> result(n + 1, -1);

    for (int e = 1, x = 0; e <= m; ++e) {
        ReachabilityChecker::limit = e;
        for (x = 1; x <= n; ++x) {
            if (result[x] > 0)
                continue;
            if (ReachabilityChecker::check(x))
                result[x] = e;
        }
    }

    for (int i = 1; i <= n; ++i)
        cout << result[i] << ' ';
    cout << '\n';
}

int main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    determineWhen();

    return 0;
}

:::

### [Subtask 3](https://hackmd.io/_V4EhjBxT8aZfBSCMuNYmQ#Subtask-3)

**Giới hạn:** $n \leq 1000$; $m \leq 4000$

#### Ý Tưởng

- [Subtask 3](https://hackmd.io/_V4EhjBxT8aZfBSCMuNYmQ#Subtask-3) có thể được giải quyết theo nhiều cách khác nhau.

##### Cách Thứ Nhất

- Ta có nhận xét rằng, với đồng xu $z$, nếu cấp bậc của $z$ có thể được xác định với tập hợp $E_i$, tập hợp của $i$ lần cân đầu tiên, thì cũng có thể được xác định với $E_j$ (với $i < j \leq m$) vì $E_i \subset E_j$.
Vì vậy, thay vì duyệt tuần tự từng tập hợp lần cân (mỗi lần xét một thêm kết quả cân) như trong [subtask 2](https://hackmd.io/_V4EhjBxT8aZfBSCMuNYmQ?both#Subtask-2), ta có thể sử dụng [thuật toán chặt nhị phân](https://wiki.vnoi.info/algo/basic/Binary-Search) để tìm được thời điểm sớm nhất.

##### Cách Thứ Hai

- Ý tưởng của cách thứ hai gần giống với [thuật toán Prim](https://cp-algorithms.com/graph/mst_prim.html) (sử dụng trong cho bài toán tìm [cây khung nhỏ nhất](https://en.wikipedia.org/wiki/Minimum_spanning_tree)).
Với mỗi cạnh $e_i$ trong đồ thị $G$ được định nghĩa trước đó, ta đặt trọng số của cạnh $e_i$ là $i$ (thời điểm cặp đồng xu mà $e_i$ đại diện được cân).
- Với một đỉnh $z$, ta đặt $V^{+}_{z}$ là tập hợp các đỉnh có thể đến được từ $z$ trong $G$ (bao gồm cả $z$).
Ta nhận thấy rằng việc tìm thời điểm sớm nhất mà tập hợp $V^{+}_{z}$ cũng sẽ tương đương với việc tối thiểu hóa trọng số lớn nhất trong cây chứa các cạnh $V^{+}_{z}$.
- Tương tự, ta đặt $V^{-}_{z}$ là tập hợp các đỉnh có thể đến được từ $z$ trong $G^{T}$ (bao gồm cả $z$).
Ta nhận thấy rằng việc tìm thời điểm sớm nhất mà tập hợp $V^{-}_{z}$ cũng sẽ tương đương với việc tối thiểu hóa trọng số lớn nhất trong cây chứa các cạnh $V^{-}_{z}$.
- Để tối thiểu hóa trong cả hai trường hợp, ta đều có thể thực hiện bằng cách:
- Khởi đầu với cây gồm một đỉnh $z$ duy nhất;
- Lần lượt chọn cạnh với trọng số nhỏ nhất nối từ một đỉnh đã thuộc cây và một đỉnh chưa thuộc cây;
Thêm cạnh và đỉnh của cạnh đó và cây;
Thực hiện nhiều lần cho đến khi ta không thể mở rộng được cây nữa.
- Nếu $V^{+}_{z} \cup V^{-}_{z} \neq V$ thì cấp bậc của $z$ không thể xác định.
Ngược lại, cấp bậc của $z$ sẽ là giá trị lớn nhất trong hai trường hợp.

#### Độ Phức Tạp

- Ý tưởng trong cách thứ nhất có thể được cài đặt với độ phức tạp thời gian $O(n \cdot \log m \cdot (n + m))$.
- Độ phức tạp có thể được phân tích gần như tương tự như trong [Subtask 2](https://hackmd.io/_V4EhjBxT8aZfBSCMuNYmQ?both#%C4%90%E1%BB%99-Ph%E1%BB%A9c-T%E1%BA%A1p23) nhưng khi này, ta chỉ xét $O(\log m)$ thay vì $O(m)$ tập hợp lần cân.
- Ý tưởng trong cách thứ hai có thể được cài đặt với độ phức tạp thời gian $O(n \cdot (n + m \log m))$.
- Ta phải xét qua $O(n)$ đỉnh.
- Với mỗi đỉnh, việc xử lý thông tin các đỉnh có độ phức tạp $O(n)$.
Nếu chúng ta sử dụng [heap](https://en.wikipedia.org/wiki/Heap_(data_structure)) để xác định cạnh với trọng số nhỏ nhất, bước xử lý sẽ có độ phức tạp $O(m \log m)$ bởi chúng ta thêm $O(m)$ cạnh vào [heap](https://en.wikipedia.org/wiki/Heap_(data_structure)) với mỗi thao có độ phức tạp $O(\log m)$.
- Ngoài ra, ý tưởng trong cách thứ hai cũng có thể được cài đặt với độ phức tạp thời gian $O(n \cdot (n + m))$ nếu ta sử dụng một mảng danh sách đánh số theo chỉ số cạnh thay vì dùng [heap](https://en.wikipedia.org/wiki/Heap_(data_structure)) bởi trọng số cạnh chỉ nằm trong đoạn từ $1$ tới $m$.

#### Code Minh Họa

:::spoiler Code C++ minh họa cho cách thứ nhất

#include <bits/stdc++.h>
using namespace std;

template<class A, class B> bool maximize(A &a, const B &b) { return (a < b) ? (a = b, true) : false; }
template<class A, class B> bool minimize(A &a, const B &b) { return (a > b) ? (a = b, true) : false; }

constexpr int MAX_N = 200'005, MAX_M = 800'005, INF = 0X3F3F3F3F, NINF = 0XC0C0C0C0;

vector<pair<int, int> > graph[MAX_N], reversedGraph[MAX_N];
int n, m, x[MAX_M], y[MAX_M];

void input() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> x[i] >> y[i];
        graph[x[i]].emplace_back(i, y[i]);
        reversedGraph[y[i]].emplace_back(i, x[i]);
    }
}

namespace ReachabilityChecker {

    bool visited[MAX_N];
    int limit;

    void runFirstDFS(const int x) {
        visited[x] = true;
        for (const auto &[e, y] : graph[x]) {
            if (visited[y] || e > limit)
                continue;
            runFirstDFS(y);
        }
    }

    void runSecondDFS(const int x) {
        visited[x] = true;
        for (const auto &[e, y] : reversedGraph[x]) {
            if (visited[y] || e > limit)
                continue;
            runSecondDFS(y);
        }
    }

    int check(const int source) {
        for (int i = 1; i <= n; ++i)
            visited[i] = false;
        runFirstDFS(source);
        runSecondDFS(source);
        for (int i = 1; i <= n; ++i)
            if (!visited[i])
                return false;
        return true;
    }

}

void determineWhen() {
    for (int x = 1, low = 0, middle = 0, high = m; x <= n; ++x) {
        ReachabilityChecker::limit = high = m;
        if (!ReachabilityChecker::check(x)) {
            cout << -1 << ' ';
            continue;
        }
        low = 0;
        while (low + 1 < high) {
            middle = low + high >> 1;
            ReachabilityChecker::limit = middle;
            if (ReachabilityChecker::check(x))
                high = middle;
            else
                low = middle;
        }
        cout << high << ' ';
    }
    cout << '\n';
}

int main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    determineWhen();

    return 0;
}

:::

:::spoiler Code C++ minh họa thứ nhất cho cách thứ hai

#include <bits/stdc++.h>
using namespace std;

template<class A, class B> bool maximize(A &a, const B &b) { return (a < b) ? (a = b, true) : false; }
template<class A, class B> bool minimize(A &a, const B &b) { return (a > b) ? (a = b, true) : false; }

constexpr int MAX_N = 200'005, MAX_M = 800'005, INF = 0X3F3F3F3F, NINF = 0XC0C0C0C0;

vector<pair<int, int> > graph[MAX_N], reversedGraph[MAX_N];
int n, m, x[MAX_M], y[MAX_M];
bool visited[MAX_N];

void input() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> x[i] >> y[i];
        graph[x[i]].emplace_back(i, y[i]);
        reversedGraph[y[i]].emplace_back(i, x[i]);
    }
}

int findEarliestTime(const int source, vector<pair<int, int> > graph[]) {
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > heap;
    int maximum = 0;

    heap.emplace(0, source);
    visited[source] = false;

    for (; !heap.empty();) {
        const auto [t, x] = heap.top();
        heap.pop();
        if (visited[x])
            continue;
        maximize(maximum, t);
        visited[x] = true;
        for (const auto &[t, y] : graph[x]) {
            if (visited[y])
                continue;
            heap.emplace(t, y);
        }
    }

    return maximum;
}

int findEarliestTime(const int source) {
    for (int i = 1; i <= n; ++i)
        visited[i] = false;
    const int maximum = max(findEarliestTime(source, graph), findEarliestTime(source, reversedGraph));
    for (int i = 1; i <= n; ++i)
        if (!visited[i])
            return -1;
    return maximum;
}

void determineWhen() {
    for (int x = 1; x <= n; ++x)
        cout << findEarliestTime(x) << ' ';
    cout << '\n';
}

int main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    determineWhen();

    return 0;
}

:::

:::spoiler Code C++ minh họa thứ hai cho cách thứ hai

#include <bits/stdc++.h>
using namespace std;

template<class A, class B> bool maximize(A &a, const B &b) { return (a < b) ? (a = b, true) : false; }
template<class A, class B> bool minimize(A &a, const B &b) { return (a > b) ? (a = b, true) : false; }

constexpr int MAX_N = 200'005, MAX_M = 800'005, INF = 0X3F3F3F3F, NINF = 0XC0C0C0C0;

vector<pair<int, int> > graph[MAX_N], reversedGraph[MAX_N];
int n, m, x[MAX_M], y[MAX_M];
bool visited[MAX_N];

void input() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> x[i] >> y[i];
        graph[x[i]].emplace_back(i, y[i]);
        reversedGraph[y[i]].emplace_back(i, x[i]);
    }
}

int findEarliestTime(const int source, vector<pair<int, int> > graph[]) {
    static queue<int> queues[MAX_M];
    int maximum = 0;

    visited[source] = false;
    queues[0].push(source);

    for (int t = 0; t <= m; ++t)
        for (; !queues[t].empty(); queues[t].pop()) {
            const auto &x = queues[t].front();
            if (visited[x])
                continue;
            maximize(maximum, t);
            visited[x] = true;
            for (const auto &[e, y] : graph[x]) {
                if (visited[y])
                    continue;
                ((e <= t) ? queues[t] : queues[e]).push(y);
            }
        }

    return maximum;
}

int findEarliestTime(const int source) {
    for (int i = 1; i <= n; ++i)
        visited[i] = false;
    const int maximum = max(findEarliestTime(source, graph), findEarliestTime(source, reversedGraph));
    for (int i = 1; i <= n; ++i)
        if (!visited[i])
            return -1;
    return maximum;
}

void determineWhen() {
    for (int x = 1; x <= n; ++x)
        cout << findEarliestTime(x) << ' ';
    cout << '\n';
}

int main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    determineWhen();

    return 0;
}

:::

### [Subtask 4](https://hackmd.io/_V4EhjBxT8aZfBSCMuNYmQ#Subtask-4)

**Giới hạn:** $n \leq 200,000$; $m \leq 800,000$

#### Ý Tưởng

- Vì dữ liệu đầu vào đảm bảo rằng các kết quả cân không mâu thuẫn với nhau, đồ thị $G$ được dựng trước đó sẽ không chứa [chu trình](https://en.wikipedia.org/wiki/Cycle_(graph_theory)). Điều này đồng nghĩa với việc $G$ là một [DAG (Directed acyclic graph)](https://en.wikipedia.org/wiki/Directed_acyclic_graph).
- Ta đặt $S$ là một [thứ tự Tô-pô](https://wiki.vnoi.info/algo/graph-theory/topological-sort.md) của $G$ và đặt $T_x$ là vị trí của $x$ trong thứ tự đó ($T_x$ có thể được xem như chỉ số của $x$ sau khi ta thực hiện [sắp xếp Tô-pô](https://cp-algorithms.com/graph/topological-sort.html)).
- Để miêu tả phần còn lại của ý tưởng dễ hơn, ta sẽ đánh số đỉnh đồ thị lại theo [thứ tự Tô-pô](https://wiki.vnoi.info/algo/graph-theory/topological-sort.md) (với mọi cung $(x, y)$ trong $G$ sau khi đã đánh số lại, ta có $x < y$).
- Ta đặt $R_x$ là chỉ số đỉnh nhỏ nhất mà có cung từ trực tiếp từ $x$ đến đỉnh đó (có thể xem như $R_x = +\infty$ nếu như $x$ không có cung đi ra).
Ta có nhận xét rằng: **với mọi đỉnh $z < x$, nếu như $R_u \leq x$ với mọi $z \leq u \leq x$ thì phải tồn tại ít nhất một đường đi từ $z$ tới $x$**.
:::spoiler Chứng minh
Nhận xét trên có thể được chứng minh bằng cách quy nạp:
- Bước cơ sở: với $z = x - 1$
- Vì $z < R_z$, ta có $x - 1 < R_z \leq x$. Nói cách khác, $R_z = x$ hay từ $z$ đến $x$ có một cung trực tiếp.
- Bước quy nạp: giả định nhận xét trên thỏa với mọi $z < u \leq x$, ta cần chứng minh nhận xét trên cũng thỏa với $z$.
- Vì $z$ có cung trực tiếp từ nó đến $R_z$ (theo như định nghĩa của $R_z$) và $R_z$ có đường đi từ nó tới $x$ (theo như giả định và $z < R_z \leq x$), $z$ có đường đi từ nó tới $x$.
:::
- Tương tự, ta đặt $L_x$ là chỉ số đỉnh lớn nhất mà có cung từ trực tiếp từ đỉnh đó đến $x$ (có thể xem như $L_x = -\infty$ nếu như không có cung đi đến $x$).
Ta có nhận xét rằng: **với mọi đỉnh $x< z$, nếu như $x \leq L_u$ với mọi $x \leq u \leq z$ thì phải tồn tại ít nhất một đường đi từ $x$ tới $z$**.
:::spoiler Chứng minh
Nhận xét trên có thể được chứng minh bằng cách quy nạp như nhận xét trước đó:
- Bước cơ sở: với $z = x + 1$
- Vì $L_z < z$, ta có $x \leq L_z < x + 1$. Nói cách khác, $L_z = x$ hay từ $x$ đến $z$ có một cung trực tiếp.
- Bước quy nạp: giả định nhận xét trên thỏa với mọi $x \leq u < z$, ta cần chứng minh nhận xét trên cũng thỏa với $z$.
- Vì $L_z$ có cung trực tiếp từ nó đến $z$ (theo như định nghĩa của $L_z$) và $L_z$ có đường đi từ $x$ tới nó (theo như giả định và $x \leq L_z < z$), $z$ có đường đi từ $x$ tới nó.
:::
- Dựa trên hai nhận xét này, nếu ta chỉ muốn kiểm tra rằng cấp bậc của một đồng xu $z$ (sau khi đã đánh số lại) có thể hay không thể được xác định (và đạt $50$% số điểm của [subtask 4](https://hackmd.io/_V4EhjBxT8aZfBSCMuNYmQ#Subtask-4)), ta cần kiểm tra cả hai điều kiện sau có thỏa không:
- Với mọi đỉnh $u$ có chỉ số nhỏ hơn $z$, $R_u \leq z$.
- Với mọi đỉnh $u$ có chỉ số lớn hơn $z$, $z \leq L_u$.
- Để xác định chính xác thời điểm sớm nhất cấp bậc của một đỉnh có thể được xác định, nếu ta thực hiện kiểm tra nêu trên nhiều lần với các tập hợp lần cân khác nhau, chi phí tính sẽ quá lớn.
- Ta đặt $C_z$ là số lượng đỉnh $u$ thỏa mãn điều kiện nếu ta đang xét đỉnh $z$ ($R_u \leq z$ nếu $u < z$ hoặc $z \leq L_u$ nếu $z < u$). Cấp bậc của đỉnh $z$ có thể xác định được ở thời điểm $C_z = n - 1$ sớm nhất.
- Ta nhận thấy rằng, nếu ta bắt đầu với một đồ thị chưa có cạnh nào và thêm dần các cạnh theo thứ tự đề bài, giả sử cạnh đang xét là $(x, y)$ thì ta sẽ chứng kiến những thay đổi này sau đây:
- $R_x$ có thể giảm thành $y$: Khi này, giá trị $C_u$ tăng thêm một đơn vị với $u$ trong đoạn từ $y$ tới $R_x - 1$.
- $L_y$ có thể tăng thành $x$: Khi này, giá trị $C_u$ tăng thêm một đơn vị với $u$ trong đoạn từ $L_x + 1$ tới $y$.
- Sau khi cập nhật các giá trị $C_u$ sau mỗi lần thêm cạnh, giá trị $C_u$ mà ta cần để ý cũng chính là giá trị $C_u$ lớn nhất (bởi $n - 1$ cũng là giá trị lớn nhất có thể của $C_u$).
- Dựa vào những nhận xét này, ta nhận thấy ta có thể sử dụng [cấu trúc dữ liệu Segment Tree với kỹ thuật Lazy Propogation](https://wiki.vnoi.info/algo/data-structures/segment-tree-extend) để quản lý thông tin bởi:
- Ta cần thực hiện update (tăng giá trị) các đoạn khác nhau
- Ta cần tìm giá trị lớn nhất trên đoạn.

#### Độ Phức Tạp

- Ý tưởng nêu trên có thể được cài đặt với độ phức tạp thời gian $O((n + m) \log n)$.
- Việc tìm [thứ tự Tô-pô](https://en.wikipedia.org/wiki/Topological_sorting) có thể được thực hiện trong $O(n + m)$.
- Vì ta cần phải duyệt qua $O(m)$ cạnh và với mỗi cạnh, ta có thể update đoạn với độ phức tạp $O(\log n)$.
- Ngoài ra, mỗi khi cấp bậc của một đỉnh được xác định, ta phải "xóa" đỉnh đó khỏi cấu trúc dữ liệu để có thể tìm được những đỉnh khác. Ta sẽ có $O(n)$ thao tác "xóa" như vậy và mỗi thao tác có thể có độ phức tạp $O(\log n)$.

#### Code Minh Họa

:::spoiler Code C++ minh họa

#include <bits/stdc++.h>
using namespace std;

template<class A, class B> bool maximize(A &a, const B &b) { return (a < b) ? (a = b, true) : false; }
template<class A, class B> bool minimize(A &a, const B &b) { return (a > b) ? (a = b, true) : false; }

constexpr int MAX_N = 200'005, MAX_M = 800'005, INF = 0X3F3F3F3F, NINF = 0XC0C0C0C0;

class SegmentTree {
private:

    vector<pair<int, int> > maximum;
    vector<int> lazyValue;
    int length;

    void pushDown(const int i) {
        if (lazyValue[i]) {
            int j = i << 1;
            maximum[j].first += lazyValue[i];
            lazyValue[j] += lazyValue[i];
            j |= 1;
            maximum[j].first += lazyValue[i];
            lazyValue[j] += lazyValue[i];
            lazyValue[i] = 0;
        }
    }

    void modify(const int q, const int value, const int i, const int l, const int r) {
        if (q < l || r < q)
            return;
        if (l == r) {
            maximum[i] = make_pair(value, r);
            return;
        }
        const int m = l + r >> 1;
        pushDown(i);
        modify(q, value, i << 1, l, m);
        modify(q, value, i << 1 | 1, m + 1, r);
        maximum[i] = max(maximum[i << 1], maximum[i << 1 | 1]);
    }

    void update(const int ql, const int qr, const int value, const int i, const int l, const int r) {
        if (qr < l || r < ql)
            return;
        if (ql <= l && r <= qr) {
            maximum[i].first += value;
            lazyValue[i] += value;
            return;
        }
        const int m = l + r >> 1;
        pushDown(i);
        update(ql, qr, value, i << 1, l, m);
        update(ql, qr, value, i << 1 | 1, m + 1, r);
        maximum[i] = max(maximum[i << 1], maximum[i << 1 | 1]);
    }

    void build(const int i, const int l, const int r) {
        if (l == r) {
            maximum[i].second = l;
            return;
        }
        const int m = l + r >> 1;
        build(i << 1, l, m);
        build(i << 1 | 1, m + 1, r);
    }

public:

    SegmentTree(int length, const int value): length(length) {
        maximum.resize(length + 1 << 2, make_pair(value, -1));
        lazyValue.resize(maximum.size());
        build(1, 1, length);
    };

    void modify(const int q, const int value) {
        modify(q, value, 1, 1, length);
    }

    void update(const int ql, const int qr, const int value) {
        update(ql, qr, value, 1, 1, length);
    }

    pair<int, int> getTop() const {
        return maximum[1];
    }

};

signed position[MAX_N], degree[MAX_N], order[MAX_N];
int n, m, x[MAX_M], y[MAX_M];
vector<int> graph[MAX_N];

void input() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> x[i] >> y[i];
        graph[x[i]].push_back(y[i]);
        ++degree[y[i]];
    }
}

void determineTopologicalOrder() {
    queue<int> q;
    int t = 0;

    for (int u = 1; u <= n; ++u)
        if (degree[u] == 0)
            q.push(u);

    for (; !q.empty(); q.pop()) {
        const int &u = q.front();
        order[position[u] = ++t] = u;
        for (const auto &v : graph[u])
            if ((--degree[v]) == 0)
                q.push(v);
    }
}

void determineTime() {
    SegmentTree segmentTree(n, 0);
    vector<int> result(n + 1, -1), maximum(n + 1, NINF), minimum(n + 1, INF);

    for (int i = 1, u = 0, v = 0; i <= m; ++i) {
        u = position[x[i]];
        v = position[y[i]];
        if (v <= minimum[u]) {
            segmentTree.update(v, minimum[u] - 1, 1);
            minimum[u] = v;
        }
        if (maximum[v] <= u) {
            segmentTree.update(maximum[v] + 1, u, 1);
            maximum[v] = u;
        }
        for (;;) {
            const auto &[f, z] = segmentTree.getTop();
            if (f < n - 1)
                break;
            result[order[z]] = i;
            segmentTree.modify(z, NINF);
        }
    }

    for (int i = 1; i <= n; ++i)
        cout << result[i] << ' ';
    cout << '\n';
}

int main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    determineTopologicalOrder();
    determineTime();

    return 0;
}

:::