CSES 1756 ↗

Acyclic Graph Edges

Orient every edge so that the resulting directed graph has no cycle.

0
submissions
—
best score

Given an undirected graph, your task is to choose a direction for each edge so that the resulting directed graph is acyclic.

Input

The first input line has two integers n and m: the number of nodes and edges. The nodes are numbered 1,2,…,n.

After this, there are m lines describing the edges. Each line has two distinct integers a and b: there is an edge between nodes a and b.

Output

Print m lines describing the directions of the edges. Each line has two integers a and b: there is an edge from node a to node b. You can print any valid solution.

Constraints

  • 1≤n≤105
  • 1≤m≤2⋅105
  • 1≤a,b≤n

Example

Input:

3 3
1 2
2 3
3 1

Output:

1 2
3 2
3 1

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/AcyclicGraphEdges/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Results

No scoring submissions yet. One counts once the kernel accepts its proof and every test passes.

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.