Overview

This problem is a simulation problem where you explore a cave starting from room \(1\), following given rules (passage priorities, room lighting colors, and visit states).

Although the exploration rules may appear complex at first glance, they are essentially Depth-First Search (DFS) itself. By simulating the exploration using appropriate data structures, the problem can be solved efficiently.

---

Analysis

1. Organizing the Rules and Reducing to DFS

Organizing the rules from the problem statement, we get the following: - Start from room \(1\), and as long as there are reachable rooms, proceed deeper through passages with higher priority (Rules 1–3). - When reaching a dead end (all passages have been checked, or no room satisfies the movement conditions), return to the room you were previously in (Rule 4: backtracking). - In the room you returned to, resume exploration from the next passage after where you left off (Rule 4).

This is exactly the behavior of a standard DFS.

2. Movement Condition Evaluation

When checking the passage from room \(u\) to room \(v\), movement is allowed only when both of the following conditions are satisfied simultaneously: 1. Room \(v\) is unvisited (visited[v] == false) 2. The lighting colors of rooms \(u\) and \(v\) are different (C[u] != C[v])

If these conditions are not met, the passage is skipped. The important point here is that “a passage that has been checked once never needs to be checked again.” This is because: - A room that has already been visited will never become unvisited again. - If a passage was skipped due to the color condition (cannot proceed because the colors are the same), since room colors do not change during exploration, it will never become possible to use that passage in the future.

Therefore, by recording how far the passages from each room \(u\) have been checked using a pointer (index), we can avoid the waste of scanning the same passage multiple times.

3. Concerns with Recursive DFS

Typically, DFS is implemented using a recursive function. However, in this problem, since the constraints are large with \(N, M \le 2 \times 10^5\), deep recursion may cause stack overflow (memory limit exceeded or abnormal termination).

For this reason, it is safe and reliable to implement non-recursive (loop-based) DFS using an explicit stack (std::vector or std::stack).

---

Algorithm

Using a stack-based non-recursive DFS, the simulation is performed as follows:

1. Graph Construction: Store the passages from each room in an adjacency list adj. Since the order given in the input directly corresponds to the priority, add them to adj[u] in the given order.

2. Exploration State Initialization:

   • Initialize an array visited that records whether each room has been visited to false.
   • For each room \(u\), initialize cur_edge_idx[u] (the index pointing to the next passage to check) to \(0\).
   • Prepare a stack st, add room \(1\) (the starting point), and set visited[1] = true.

3. Exploration Loop: Repeat the following process until the stack is empty:

   • Retrieve the element at the top of the stack (current room \(u\)) (only reference, do not pop).
   • If cur_edge_idx[u] < adj[u].size() (there are still unchecked passages):
     • Get the next candidate destination \(v = \text{adj}[u][\text{cur\_edge\_idx}[u]]\).
     • Important: Increment cur_edge_idx[u] by \(1\) so that when returning to this room later, exploration resumes from the next passage.
     • Check whether the movement conditions (\(v\) is unvisited, and \(C_u \neq C_v\)) are satisfied.
     • If the conditions are met, set visited[v] = true, push \(v\) onto the stack, and proceed to the next loop iteration (exploring room \(v\)).
     • If the conditions are not met, do nothing and proceed to the next loop iteration (checking the next passage from room \(u\)).
   • If cur_edge_idx[u] == adj[u].size() (all passages have been checked):
     • Pop \(u\) from the stack (backtrack). This allows returning to the room you were previously in.

4. Output Results: After exploration ends, collect room numbers where visited[i] is false in ascending order. If there are none, output COMPLETE; otherwise, output those room numbers separated by spaces.

---

Complexity

• Time Complexity: \(O(N + M)\) Each room is pushed onto the stack at most once. Also, each passage (edge) is scanned at most once due to cur_edge_idx, so the total number of transitions is \(O(N + M)\), which is well within the time limit.

• Space Complexity: \(O(N + M)\) \(O(N + M)\) memory is used for storing the adjacency list, and \(O(N)\) for the visited flags, stack, and passage index storage.

---

Implementation Notes

• Persistence of cur_edge_idx: When backtracking and returning to the same room, exploration needs to “resume from where it was interrupted.” By managing cur_edge_idx outside the stack (globally or within the main function), the state is correctly maintained even after backtracking.

• I/O Optimization: In C++, since the input data size is large (\(N, M \le 2 \times 10^5\)), it is recommended to include cin.tie(NULL); ios_base::sync_with_stdio(false); to speed up input/output.

  Source Code

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<int> C(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> C[i];
    }

    // 隣接リストの構築（入力順がそのまま優先順位となる）
    vector<vector<int>> adj(N + 1);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }

    vector<bool> visited(N + 1, false);
    vector<size_t> cur_edge_idx(N + 1, 0);

    // 非再帰DFSのためのスタック
    vector<int> st;

    // 部屋 1 から探索を開始
    visited[1] = true;
    st.push_back(1);

    while (!st.empty()) {
        int u = st.back();

        // 現在の部屋 u から出る通路を順に確認
        if (cur_edge_idx[u] < adj[u].size()) {
            int v = adj[u][cur_edge_idx[u]];
            cur_edge_idx[u]++; // 次回再開時は次の通路から

            if (visited[v]) {
                continue;
            }
            if (C[u] == C[v]) {
                continue;
            }

            // 移動条件を満たす場合、移動して訪問済みにする
            visited[v] = true;
            st.push_back(v);
        } else {
            // すべての通路を確認し終えたらバックトラック
            st.pop_back();
        }
    }

    // 一度も訪れなかった部屋を収集
    vector<int> unvisited;
    for (int i = 1; i <= N; ++i) {
        if (!visited[i]) {
            unvisited.push_back(i);
        }
    }

    // 結果の出力
    if (unvisited.empty()) {
        cout << "COMPLETE\n";
    } else {
        for (size_t i = 0; i < unvisited.size(); ++i) {
            cout << unvisited[i] << (i + 1 == unvisited.size() ? "" : " ");
        }
        cout << "\n";
    }

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-thinking.