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

My submissions

/
/
/
/

Announcements

My submissions

/
/
/
/

Announcements

Solve
Author

W1D5B. Almost One-Way Tour (Hard Version)

2 pts·4s·256 MB

Constraints

Input

Output

Samples

Input
5
3 3
1 2
2 3
3 1
4 6
1 3
3 2
2 4
4 1
1 2
3 4
5 8
2 5
5 1
1 4
4 3
3 2
5 4
3 1
1 2
6 12
1 3
3 5
5 1
2 4
4 6
6 2
1 2
2 3
3 4
4 5
5 6
6 1
7 12
4 1
1 6
6 2
2 7
7 3
3 5
5 4
1 2
6 7
3 4
5 6
7 5
Explanation
Case 1
Case 2
Case 3
Case 4
Case 5
Output
1 2 3
1 3 2 4
1 4 3 2 5
1 3 5 2 4 6
1 6 2 7 3 5 4

You are given a simple directed graph with nnn vertices, numbered from 111 to nnn.

For every two distinct vertices uuu and vvv, the graph does not contain both edges u→vu \to vu→v and v→uv \to uv→u.

It is guaranteed that the graph contains a directed Hamiltonian cycle.

Find a cyclic ordering p1,p2,…,pnp_1,p_2,\ldots,p_np1​,p2​,…,pn​ of all vertices. An index iii is called good if the graph contains the edge pi→pi+1p_i \to p_{i+1}pi​→pi+1​, where pn+1=p1p_{n+1}=p_1pn+1​=p1​.

Your ordering must have at least ⌈2n3⌉\left\lceil \frac{2n}{3} \right\rceil⌈32n​⌉ good indices.

  • 1≤t≤1041 \le t \le 10^41≤t≤104
  • 3≤n≤2×1053 \le n \le 2 \times 10^53≤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 u,vu,vu,v, at most one of u→vu \to vu→v and v→uv \to uv→u exists
  • Every graph contains a directed Hamiltonian cycle
  • The sum of nnn over all test cases is at most 2×1052 \times 10^52×105
  • The sum of mmm over all test cases is at most 2×1052 \times 10^52×105
ttt nmu1v1u2v2⋮umvm}×t\left. \begin{array}{l} n \quad m \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array} \right\} \times tnmu1​v1​u2​v2​⋮um​vm​​⎭⎬⎫​×t
p1p2⋯pn}×t\left. \begin{array}{l} p_1 \quad p_2 \quad \cdots \quad p_n \end{array} \right\} \times tp1​p2​⋯pn​​}×t

For each test case, output any cyclic ordering satisfying the requirement.

The ordering contains every vertex once. All three cyclic consecutive pairs, including 3→13 \to 13→1, are edges of the graph.

The cyclic consecutive pairs are 1→31 \to 31→3, 3→23 \to 23→2, 2→42 \to 42→4, and 4→14 \to 14→1, so all four indices are good.

The ordering follows the directed cycle 1→4→3→2→5→11 \to 4 \to 3 \to 2 \to 5 \to 11→4→3→2→5→1, giving five good indices.

Five indices are good: the graph contains 1→31 \to 31→3, 3→53 \to 53→5, 2→42 \to 42→4, 4→64 \to 64→6, and 6→16 \to 16→1. The pair 5→25 \to 25→2 does not need to be an edge.

The ordering follows the directed cycle 1→6→2→7→3→5→4→11 \to 6 \to 2 \to 7 \to 3 \to 5 \to 4 \to 11→6→2→7→3→5→4→1, so every index is good.