Repovive
  • Dashboard
  • Ranking
  • Submissions
  • Discussion
  1. Contests
  2. Weekly Challenge 1: Approximation
  3. W1D6B

My submissions

/
/
/
/

Announcements

My submissions

/
/
/
/

Announcements

Solve
Author

W1D6B. Almost Rainbow Tree (Hard Version)

2 pts·3s·256 MB

Constraints

Input

Output

Samples

Input
7 10
1 2 1
2 3 2
3 4 3
1 3 4
1 4 5
2 4 6
1 5 1
2 6 2
3 7 3
5 6 2
Explanation
Output
6
4 5 6 7 8 9

You are given a connected undirected graph with nnn vertices and mmm edges. The edges are numbered from 111 to mmm. Edge iii connects uiu_iui​ and viv_ivi​ and has color cic_ici​.

It is guaranteed that the graph has a spanning tree whose n−1n-1n−1 edges have pairwise distinct colors.

Choose some edges such that:

  • the chosen edges contain no cycle;
  • no two chosen edges have the same color.

Let sss be the number of chosen edges. Your output will be accepted if 3s≥2(n−1)3s \ge 2(n-1)3s≥2(n−1).

Output sss followed by the indices of the chosen edges. You may output any set of edges satisfying these conditions.

  • 2≤n≤3002 \le n \le 3002≤n≤300
  • n−1≤m≤min⁡(2000,n(n−1)2)n-1 \le m \le \min\left(2000, \frac{n(n-1)}{2}\right)n−1≤m≤min(2000,2n(n−1)​)
  • 1≤ui,vi≤n1 \le u_i,v_i \le n1≤ui​,vi​≤n
  • ui≠viu_i \ne v_iui​=vi​
  • 1≤ci≤m1 \le c_i \le m1≤ci​≤m
  • The graph has no multiple edges
  • The graph has a spanning tree whose edges have pairwise distinct colors
nmu1v1c1u2v2c2⋮umvmcm\begin{array}{l} n \quad m \\ u_1 \quad v_1 \quad c_1 \\ u_2 \quad v_2 \quad c_2 \\ \vdots \\ u_m \quad v_m \quad c_m \end{array}nmu1​v1​c1​u2​v2​c2​⋮um​vm​cm​​
si1i2⋯is\begin{array}{l} s \\ i_1 \quad i_2 \quad \cdots \quad i_s \end{array}si1​i2​⋯is​​

The selected edges connect all seven vertices and contain no cycle. Their colors, in the displayed order, are 4,5,6,1,2,34,5,6,1,2,34,5,6,1,2,3, which are pairwise distinct. Also, 3⋅6≥2⋅(7−1)3\cdot 6 \ge 2\cdot(7-1)3⋅6≥2⋅(7−1).