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

My submissions

/
/
/
/

Announcements

My submissions

/
/
/
/

Announcements

Solve
Author

W1D2A. Far Enough

1 pts·1s·256 MB

Constraints

Input

Output

Samples

Input
1
6 7
1 2
2 3
3 4
4 5
5 6
6 1
1 4
Explanation
Output
1 6

You are given a strongly connected directed graph with nnn vertices and mmm edges.

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

The directed diameter of the graph is the maximum value of dist(u,v)dist(u,v)dist(u,v) over all ordered pairs of vertices (u,v)(u,v)(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 DDD be the directed diameter of the graph. You have to output two vertices aaa and bbb such that 2×dist(a,b)≥D2 \times dist(a,b) \ge D2×dist(a,b)≥D.

  • 1≤t≤51 \le t \le 51≤t≤5
  • 2≤n≤60002 \le n \le 60002≤n≤6000
  • n≤m≤100000n \le m \le 100000n≤m≤100000
  • The sum of nnn over all test cases is at most 600060006000
  • The sum of mmm over all test cases is at most 100000100000100000
  • The graph is strongly connected
  • There are no self-loops or multiple directed edges

The input is given in the following format:

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

Each edge is directed from uiu_iui​ to viv_ivi​.

For each test case, output two integers aaa and bbb, describing the ordered pair of vertices you choose.

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

The output format is:

ab}×t\left. \begin{array}{l} a \quad b \end{array} \right\} \times tab​}×t

There is a directed path from 111 to 666 with length 333: 1→4→5→61 \to 4 \to 5 \to 61→4→5→6.

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