Almost Rainbow Tree (Hard Version) - Weekly Challenge 1: Approximation | Repovive

W1D6B. Almost Rainbow Tree (Hard Version)

2 pts3s256 MB

You are given a connected undirected graph with $n$ vertices and $m$ edges. The edges are numbered from $1$ to $m$ . Edge $i$ connects $u_i$ and $v_i$ and has color $c_i$ .

It is guaranteed that the graph has a spanning tree whose $n-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 $s$ be the number of chosen edges. Your output will be accepted if $3s \ge 2(n-1)$ .

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

Constraints

$2 \le n \le 300$
$n-1 \le m \le \min\left(2000, \frac{n(n-1)}{2}\right)$
$1 \le u_i,v_i \le n$
$u_i \ne v_i$
$1 \le c_i \le m$
The graph has no multiple edges
The graph has a spanning tree whose edges have pairwise distinct colors

Input

\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}

Output

\begin{array}{l} s \\ i_1 \quad i_2 \quad \cdots \quad i_s \end{array}

Samples

Input

Explanation

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

Output

6
4 5 6 7 8 9

You are given a connected undirected graph with $n$ vertices and $m$ edges. The edges are numbered from $1$ to $m$ . Edge $i$ connects $u_i$ and $v_i$ and has color $c_i$ .

It is guaranteed that the graph has a spanning tree whose $n-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 $s$ be the number of chosen edges. Your output will be accepted if $3s \ge 2(n-1)$ .

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

$2 \le n \le 300$
$n-1 \le m \le \min\left(2000, \frac{n(n-1)}{2}\right)$
$1 \le u_i,v_i \le n$
$u_i \ne v_i$
$1 \le c_i \le m$
The graph has no multiple edges
The graph has a spanning tree whose edges have pairwise distinct colors

\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}

\begin{array}{l} s \\ i_1 \quad i_2 \quad \cdots \quad i_s \end{array}

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

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

W1D6B. Almost Rainbow Tree (Hard Version)

Constraints

Input

Output

Samples

W1D6B. Almost Rainbow Tree (Hard Version)

Constraints

Input

Output

Samples