Almost One-Way Tour (Hard Version) - Weekly Challenge 1: Approximation | Repovive

W1D5B. Almost One-Way Tour (Hard Version)

2 pts4s256 MB

You are given a simple directed graph with $n$ vertices, numbered from $1$ to $n$ .

For every two distinct vertices $u$ and $v$ , the graph does not contain both edges $u \to v$ and $v \to u$ .

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

Find a cyclic ordering $p_1,p_2,\ldots,p_n$ of all vertices. An index $i$ is called good if the graph contains the edge $p_i \to p_{i+1}$ , where $p_{n+1}=p_1$ .

Your ordering must have at least $\left\lceil \frac{2n}{3} \right\rceil$ good indices.

Constraints

$1 \le t \le 10^4$
$3 \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,v$ , at most one of $u \to v$ and $v \to u$ exists
Every graph contains a directed Hamiltonian cycle
The sum of $n$ over all test cases is at most $2 \times 10^5$
The sum of $m$ over all test cases is at most $2 \times 10^5$

Input

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 t

Output

\left. \begin{array}{l} p_1 \quad p_2 \quad \cdots \quad p_n \end{array} \right\} \times t

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

Samples

Input

Explanation

Case 1

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

Case 2

The cyclic consecutive pairs are $1 \to 3$ , $3 \to 2$ , $2 \to 4$ , and $4 \to 1$ , so all four indices are good.

Case 3

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

Case 4

Five indices are good: the graph contains $1 \to 3$ , $3 \to 5$ , $2 \to 4$ , $4 \to 6$ , and $6 \to 1$ . The pair $5 \to 2$ does not need to be an edge.

Case 5

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

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 $n$ vertices, numbered from $1$ to $n$ .

For every two distinct vertices $u$ and $v$ , the graph does not contain both edges $u \to v$ and $v \to u$ .

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

Find a cyclic ordering $p_1,p_2,\ldots,p_n$ of all vertices. An index $i$ is called good if the graph contains the edge $p_i \to p_{i+1}$ , where $p_{n+1}=p_1$ .

Your ordering must have at least $\left\lceil \frac{2n}{3} \right\rceil$ good indices.

$1 \le t \le 10^4$
$3 \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,v$ , at most one of $u \to v$ and $v \to u$ exists
Every graph contains a directed Hamiltonian cycle
The sum of $n$ over all test cases is at most $2 \times 10^5$
The sum of $m$ over all test cases is at most $2 \times 10^5$

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 t

\left. \begin{array}{l} p_1 \quad p_2 \quad \cdots \quad p_n \end{array} \right\} \times 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 \to 1$ , are edges of the graph.

The cyclic consecutive pairs are $1 \to 3$ , $3 \to 2$ , $2 \to 4$ , and $4 \to 1$ , so all four indices are good.

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

Five indices are good: the graph contains $1 \to 3$ , $3 \to 5$ , $2 \to 4$ , $4 \to 6$ , and $6 \to 1$ . The pair $5 \to 2$ does not need to be an edge.

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

	#	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

W1D5B. Almost One-Way Tour (Hard Version)

Constraints

Input

Output

Samples

W1D5B. Almost One-Way Tour (Hard Version)

Constraints

Input

Output

Samples