## Bob Hates Triangles

View as PDF

Points: 7
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types

Bob got an undirected graph for his birthday! As part of his birthday present, he gets to direct the edges in his graph!

Bob hates triangles. He has decided to direct the edges of his graph such that there is a minimum number of triangles, but he's not sure how. Can you help him?

Note: A triangle is a set of distinct points such that the edges , and all exist.

#### Input Specification

The first line will contain and separated by a space, the number of nodes and edges.

The next lines will contain and , a directed edge connecting and .

#### Output Specification

Output lines that contain and for each of the edges after directing them. The edges can be outputted in any order.

If there are multiple direction configurations that give a minimum number of triangles, you may output any of them.

#### Sample Input

5 4
1 2
4 3
3 2
1 3

#### Sample Output

1 2
3 2
4 3
3 1