Far Enough - Testing Approx Problems | Repovive

1012C. Far Enough

1s256 MB

You are given a strongly connected directed graph with $n$ vertices and $m$ edges.

For two vertices $u$ and $v$ , let $dist(u,v)$ be the minimum number of edges in a directed path from $u$ to $v$ .

The directed diameter of the graph is the maximum value of $dist(u,v)$ over all ordered pairs of vertices $(u,v)$ .

You do not need to find the directed diameter exactly. You only need to output an ordered pair of vertices whose distance is at least half of the directed diameter.

More formally, let $D$ be the directed diameter of the graph. You have to output two vertices $a$ and $b$ such that $2 \times dist(a,b) \ge D$ .

Constraints

$1 \le t \le 5$
$2 \le n \le 6000$
$n \le m \le 100000$
The sum of $n$ over all test cases is at most $6000$
The sum of $m$ over all test cases is at most $100000$
The graph is strongly connected
There are no self-loops or multiple directed edges

Input

The input is given in the following format:

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

Each edge is directed from $u_i$ to $v_i$ .

Output

For each test case, output two integers $a$ and $b$ , describing the ordered pair of vertices you choose.

If the directed diameter of the graph is $D$ , your output must satisfy $2 \times dist(a,b) \ge D$ .

The output format is:

\left. \begin{array}{l} a \quad b \end{array} \right\} \times t

Samples

Input

Explanation

There is a directed path from $1$ to $6$ with length $3$ : $1 \to 4 \to 5 \to 6$ .

The pair $(2,1)$ has distance $5$ , so the shown output is not optimal. Still, the shown distance is enough because $2 \times 3 \ge 5$ .

Output

1 6

You are given a strongly connected directed graph with $n$ vertices and $m$ edges.

For two vertices $u$ and $v$ , let $dist(u,v)$ be the minimum number of edges in a directed path from $u$ to $v$ .

The directed diameter of the graph is the maximum value of $dist(u,v)$ over all ordered pairs of vertices $(u,v)$ .

You do not need to find the directed diameter exactly. You only need to output an ordered pair of vertices whose distance is at least half of the directed diameter.

More formally, let $D$ be the directed diameter of the graph. You have to output two vertices $a$ and $b$ such that $2 \times dist(a,b) \ge D$ .

$1 \le t \le 5$
$2 \le n \le 6000$
$n \le m \le 100000$
The sum of $n$ over all test cases is at most $6000$
The sum of $m$ over all test cases is at most $100000$
The graph is strongly connected
There are no self-loops or multiple directed edges

The input is given in the following format:

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

Each edge is directed from $u_i$ to $v_i$ .

For each test case, output two integers $a$ and $b$ , describing the ordered pair of vertices you choose.

If the directed diameter of the graph is $D$ , your output must satisfy $2 \times dist(a,b) \ge D$ .

The output format is:

\left. \begin{array}{l} a \quad b \end{array} \right\} \times t

There is a directed path from $1$ to $6$ with length $3$ : $1 \to 4 \to 5 \to 6$ .

The pair $(2,1)$ has distance $5$ , so the shown output is not optimal. Still, the shown distance is enough because $2 \times 3 \ge 5$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

1012C. Far Enough

Constraints

Input

Output

Samples

1012C. Far Enough

Constraints

Input

Output

Samples