Bob Hates Triangles

View as PDF

Submit solution

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

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 (a, b, c) such that the edges (a, b), (b, c) and (c, a) all exist.

Input Specification

The first line will contain N (1 \le N \le 2 \times 10^5) and M (1 \le M \le 2 \times 10^5) separated by a space, the number of nodes and edges.

The next M lines will contain u and v (1 \le u, v \le N, u \ne v), a directed edge connecting u and v.

Output Specification

Output M lines that contain u and v 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


There are no comments at the moment.