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

My submissions

/
/
/
/

Announcements

My submissions

/
/
/
/

Announcements

Solve
Author

W1D7B. Strong Enough (Hard Version)

2 pts·4s·256 MB

Constraints

Input

Output

Samples

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

You are given a simple directed graph with nnn vertices and mmm edges. The vertices are numbered from 111 to nnn, and the edges are numbered from 111 to mmm in the order in which they appear in the input.

The graph has the following properties:

  • for every pair of distinct vertices uuu and vvv, at most one of the edges u→vu \to vu→v and v→uv \to uv→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 nnn vertices, is strongly connected.

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

  • 4≤n≤2×1054 \le n \le 2 \times 10^54≤n≤2×105
  • n≤m≤min⁡(2×105,n(n−1)2)n \le m \le \min\left(2 \times 10^5,\frac{n(n-1)}{2}\right)n≤m≤min(2×105,2n(n−1)​)
  • 1≤ui,vi≤n1 \le u_i,v_i \le n1≤ui​,vi​≤n
  • ui≠viu_i \ne v_iui​=vi​
  • All directed edges are distinct
  • For every pair of distinct vertices uuu and vvv, at most one of u→vu \to vu→v and v→uv \to uv→u exists
  • The graph contains no directed cycle with exactly three vertices
  • The graph contains a directed Hamiltonian cycle
nmn \quad mnm u1v1u2v2⋮umvm\begin{array}{l} u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array}u1​v1​u2​v2​⋮um​vm​​
ke1e2⋯ek\begin{array}{l} k \\ e_1 \quad e_2 \quad \cdots \quad e_k \end{array}ke1​e2​⋯ek​​

Output kkk followed by kkk distinct integers e1,e2,…,eke_1,e_2,\ldots,e_ke1​,e2​,…,ek​, the indices of the chosen edges, in any order.

Your output must satisfy 2k≤3n2k \le 3n2k≤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→2→3→4→5→6→7→8→11 \to 2 \to 3 \to 4 \to 5 \to 6 \to 7 \to 8 \to 11→2→3→4→5→6→7→8→1. Therefore, the chosen subgraph is strongly connected.