Strong Enough (Hard Version) - Weekly Challenge 1: Approximation | Repovive

W1D7B. Strong Enough (Hard Version)

2 pts4s256 MB

You are given a simple directed graph with $n$ vertices and $m$ edges. The vertices are numbered from $1$ to $n$ , and the edges are numbered from $1$ to $m$ in the order in which they appear in the input.

The graph has the following properties:

for every pair of distinct vertices $u$ and $v$ , at most one of the edges $u \to v$ and $v \to u$ exists;
the graph contains no directed cycle with exactly three vertices;
the graph contains a directed Hamiltonian cycle.

Choose some of the given edges so that the directed graph formed by the chosen edges, on all $n$ vertices, is strongly connected.

In the Hard Version, if the number of chosen edges is $k$ , it must satisfy $2k \le 3n$ .

Constraints

$4 \le n \le 2 \times 10^5$
$n \le m \le \min\left(2 \times 10^5,\frac{n(n-1)}{2}\right)$
$1 \le u_i,v_i \le n$
$u_i \ne v_i$
All directed edges are distinct
For every pair of distinct vertices $u$ and $v$ , at most one of $u \to v$ and $v \to u$ exists
The graph contains no directed cycle with exactly three vertices
The graph contains a directed Hamiltonian cycle

Input

n \quad m

\begin{array}{l} u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array}

Output

\begin{array}{l} k \\ e_1 \quad e_2 \quad \cdots \quad e_k \end{array}

Output $k$ followed by $k$ distinct integers $e_1,e_2,\ldots,e_k$ , the indices of the chosen edges, in any order.

Your output must satisfy $2k \le 3n$ , and the graph formed by the chosen edges must be strongly connected.

The integers may be separated by arbitrary whitespace.

Samples

Input

Explanation

The chosen edges form the directed cycle $1 \to 2 \to 3 \to 4 \to 5 \to 6 \to 7 \to 8 \to 1$ . Therefore, the chosen subgraph is strongly connected.

Output

8
1 2 3 9 5 6 7 10

The graph has the following properties:

for every pair of distinct vertices $u$ and $v$ , at most one of the edges $u \to v$ and $v \to u$ exists;
the graph contains no directed cycle with exactly three vertices;
the graph contains a directed Hamiltonian cycle.

Choose some of the given edges so that the directed graph formed by the chosen edges, on all $n$ vertices, is strongly connected.

In the Hard Version, if the number of chosen edges is $k$ , it must satisfy $2k \le 3n$ .

$4 \le n \le 2 \times 10^5$
$n \le m \le \min\left(2 \times 10^5,\frac{n(n-1)}{2}\right)$
$1 \le u_i,v_i \le n$
$u_i \ne v_i$
All directed edges are distinct
For every pair of distinct vertices $u$ and $v$ , at most one of $u \to v$ and $v \to u$ exists
The graph contains no directed cycle with exactly three vertices
The graph contains a directed Hamiltonian cycle

n \quad m

\begin{array}{l} u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array}

\begin{array}{l} k \\ e_1 \quad e_2 \quad \cdots \quad e_k \end{array}

Output $k$ followed by $k$ distinct integers $e_1,e_2,\ldots,e_k$ , the indices of the chosen edges, in any order.

Your output must satisfy $2k \le 3n$ , and the graph formed by the chosen edges must be strongly connected.

The integers may be separated by arbitrary whitespace.

The chosen edges form the directed cycle $1 \to 2 \to 3 \to 4 \to 5 \to 6 \to 7 \to 8 \to 1$ . Therefore, the chosen subgraph is strongly connected.

	#	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

W1D7B. Strong Enough (Hard Version)

Constraints

Input

Output

Samples

W1D7B. Strong Enough (Hard Version)

Constraints

Input

Output

Samples