Overview

This problem asks you to simulate traversing cities under the rule “prioritize the unvisited city with the highest importance,” and output the sequence of city numbers in the order they are surveyed. By fixing the importance ordering through preprocessing, the simulation can be executed efficiently.

Discussion

There are two types of “maximum” selections needed in this problem:

1. During a tour: Among unvisited cities reachable by one edge from city \(u\), move to the city with the highest importance \(B\).
2. Starting a tour: For the 2nd tour onward, start from the unvisited city with the highest importance \(B\).

Issues with a naive approach

• If we select the starting city each time by “searching all unvisited cities for the maximum \(B\),” this takes \(O(N)\) per tour start, and repeating this for each tour results in \(O(N^2)\) total, causing TLE (\(N \le 2\times 10^5\)).
• Finding “the maximum \(B\) among adjacent cities” during a tour also requires searching for the maximum each time. However, since each city becomes the “current city” only once (explained below), with some ingenuity this can be done in \(O(M)\) total.

Key observations

• The importance values \(B_i\) form a permutation (all distinct), so once we create a “list of cities in decreasing order of importance,” selecting the starting city simply requires scanning this list from the front to find the first unvisited city.
• Since tours “only move to unvisited cities,” each city is visited at most once (we never return to an already surveyed city).
  Therefore, the process of finding “where to go next from \(u\)” only needs to happen once — when city \(u\) is visited.

With these two points, we can speed up both “selecting the starting city” and “selecting the best adjacent city” through preprocessing, making the overall solution fast enough.

Algorithm

Preprocessing

1. Read the importance array \(B[i]\).
2. Create a reverse lookup inv[b] that maps importance value \(b\) to its city number (possible since \(B\) is a permutation).
3. Add each directed edge \(u \to v\) to the adjacency list adj[u].
4. For each city \(u\), sort adj[u] in descending order of \(B[v]\).
   This way, “the unvisited destination with the highest importance” can be found by simply taking the first unvisited entry from the front.

Additionally, create an array of cities sorted in descending order of importance: [ \text{order_by_B} = [\text{city with importance }N, \text{city with importance }N-1, \dots] ] using inv.

Tour

Implement tour(start) as follows:

• Start with cur = start
• Mark cur as surveyed and append it to the output sequence
• Scan adj[cur] (sorted in descending importance) from the front, and find the first “unvisited” vertex nxt
  • If found, set cur = nxt and continue
  • If not found, end the tour

Overall flow

1. First, execute tour(1) (as specified by the problem).
2. While there are still unsurveyed cities:
   • Scan order_by_B from the front to find an unvisited city (simply advance the pointer pos)
   • Execute tour(that city) with it as the starting city

This produces the survey order exactly according to the rules.

Complexity

• Time complexity:
  Sorting the adjacency lists takes \(\sum_u O(\deg(u)\log \deg(u)) \le O(M\log M)\).
  The simulation part processes each city only once and traverses each edge at most once, totaling \(O(N+M)\).
  Therefore, the overall complexity is \(O(M\log M + N + M)\) (the dominant term is typically \(O(M\log M)\)).
• Space complexity: \(O(N+M)\) (adjacency lists, visit tracking, auxiliary arrays)

Implementation Notes

• Sorting adjacency lists in descending order of \(B\) allows “the maximum unvisited adjacent city” to be found via a linear scan from the front.

• Starting city selection uses the descending importance array order_by_B and a pointer pos, avoiding a full search each time (just advance pos until an unvisited city is found).

• Since the input can be large, in Python using sys.stdin.buffer.read() for fast input is effective.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = 0
    N = data[it]; it += 1
    M = data[it]; it += 1

    B = [0] * (N + 1)
    inv = [0] * (N + 1)
    for i in range(1, N + 1):
        b = data[it]; it += 1
        B[i] = b
        inv[b] = i

    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = data[it]; v = data[it + 1]; it += 2
        adj[u].append(v)

    key = B.__getitem__
    for u in range(1, N + 1):
        if adj[u]:
            adj[u].sort(key=key, reverse=True)

    order_by_B = [inv[r] for r in range(N, 0, -1)]
    pos = 0

    visited = [False] * (N + 1)
    out = []

    def tour(start: int):
        cur = start
        while True:
            visited[cur] = True
            out.append(cur)
            nxt = 0
            for v in adj[cur]:
                if not visited[v]:
                    nxt = v
                    break
            if nxt == 0:
                break
            cur = nxt

    tour(1)

    while len(out) < N:
        while pos < N and visited[order_by_B[pos]]:
            pos += 1
        tour(order_by_B[pos])

    sys.stdout.write(" ".join(map(str, out)))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.