Forest Mycelium Delay Tour

This is an Agentics migration of Frontier-CS algorithmic problem 304.

Your submitted zip_project run command is executed once per case. It receives exactly one case on stdin and must write the candidate answer to stdout. Do not read or write challenge-owned files. Network access is unavailable during setup, build, and run.

The trusted separated evaluator uses the original Frontier-CS Testlib checker. Public validation is intentionally small and only checks the interface. Official scoring uses the private Frontier-CS-derived run manifest.

Original Statement

Forest Mycelium Delay Tour (Optimization Challenge)

Problem

Vasya is mapping a forest trail network with mushroom clearings.

The forest is modeled as an undirected connected graph with N clearings (vertices) and M trails (edges).
At clearing i, mushrooms grow at a constant rate r[i] grams per minute, starting from 0 grams at time 0.

• Vasya starts at clearing 1 at time t = 0.
• Each minute, Vasya must traverse exactly one trail to an adjacent clearing (no waiting).
• When Vasya first arrives at a clearing i at time t, he instantly collects all mushrooms grown there so far, equal to r[i] * t grams.
• After the first collection at clearing i, that clearing becomes barren and yields 0 on future visits.
• Vasya will walk for exactly K minutes (i.e., traverse exactly K edges), ending anywhere.
• To be feasible, his walk must visit every clearing at least once during times 0..K.

Your goal is to output a feasible walk that maximizes the total collected mushroom weight.

This is an open-ended optimization task: many solutions are valid, and they receive different scores.

Input

N M K
r1 r2 ... rN
u1 v1
u2 v2
...
uM vM

• 1 ≤ N ≤ 20000
• N-1 ≤ M ≤ 60000
• 2·(N-1) ≤ K ≤ 200000
• 1 ≤ r[i] ≤ 10^6
• 1 ≤ uj, vj ≤ N, uj != vj
• The graph is connected.
• Multiple edges may appear; self-loops do not appear.

The constraints guarantee that a walk of length K visiting all vertices exists.

Output

Output exactly K integers:

x1 x2 ... xK

where xt is the clearing Vasya is at after minute t (after the t-th move).

Feasibility requirements:

• Vasya starts at clearing 1 at time 0.
• For each t = 1..K, the move from the previous clearing to xt must follow an existing trail (edge).
• Every clearing 1..N must appear at least once among the visited clearings at times 0..K (including the start at time 0).

If the output is infeasible, the solution receives 0 score for that test.

Objective

Let pos(t) be Vasya’s clearing at time t (pos(0)=1, pos(t)=xt for t≥1).

For each clearing i, define its first-visit time:

• T[i] = min { t ∈ [0..K] | pos(t) = i }

Total collected weight: [ V = \sum_{i=1}^{N} r[i] \cdot T[i] ] (Notice T[1]=0, so clearing 1 contributes 0.)

You must maximize V.

Scoring

Scoring is computed per test.

Reference value B

For each test, the judge computes a deterministic internal reference walk from the same instance, and lets B be the objective value of that walk.

Per-test score

If V = 0, the per-test ratio is defined as 0.

Otherwise, for your solution value V, the per-test ratio is: [ \mathrm{ratio} = \mathrm{clamp}\left(\frac{V - B}{V},, 0,, 1\right) ] where clamp(x,0,1)=min(1,max(0,x)).

Total score

The final score is the sum of per-test ratios, scaled to the total points configured for this problem.

Constraints

• Time limit: 2 seconds
• Memory limit: 256 MB

Example

Sample input:

4 4 6
5 1 4 10
1 2
2 3
3 4
1 4

One valid sample output:

2 3 2 1 4 3

Explanation (high level):

• Path: time 0 at 1, time 1 at 2, time 2 at 3, time 3 at 2, time 4 at 1, time 5 at 4, time 6 at 3.
• First-visit times: T[1]=0, T[2]=1, T[3]=2, T[4]=5.
• Objective value: V = 5·0 + 1·1 + 4·2 + 10·5 = 59.
• The judge also computes the baseline value B for this test, then assigns a normalized ratio using the formula above.