Here is a problem I thought of. This is just for others' interest, maybe to help them pass the time. I thought of this problem initially because I wanted to put it in a contest, however it turned to be too hard for me and a few others so it shouldn't be in a contest:

you need to construct a permutation of length N. you're given M pairs of integers (each pair contains 2 distinct elements, both are between 1 and N). the permutation you construct needs to have the following value minimized: for each pair {X1, X2}, add up to the total sum the distance (indicies distance) between the values {X1, X2}. you can print any correct answer is multiple ones exist.

input:
N M
M pairs, described in the statement
output:
the minimized value described in the statement on the 1st line, and the permutation on the 2nd one.

examples:
input:
3 2
1 2
3 1
output:
2
3 1 2

input:
4 4
1 2
4 2
3 1
3 4
output:
6
2 1 4 3