Bob Hates Triangles

View as PDF

Submit solution

All submissions

Best submissions

Points: 7

Time limit: 1.0s

Memory limit: 256M

Author:

Riolku

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

Input Specification

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

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

Output Specification

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

Sample Output

Comments

16

Jinx commented on Jan. 12, 2022, 10:06 p.m.

A better question is, why would you get your kid a graph for his birthday?