HackerEarth Friendship value problem solution

In this HackerEarth Friendship value problem solution, You want to place k people in a place shaped like a graph. The graph has n vertices and m edges.

The score of an arrangement is based on the following two factors:

Friendship is always important even in these tough times of Covid. Here, the ith person has friendship value fi. A connected component of people with the sum of friendship value equal to s adds s*s to score. A connected component is a set of people adjacent to each other. Two persons are adjacent if they are connected with an edge.

You also need to take care of the health of people. Here, the ith person has a danger value di. Two adjacent people i and j reduce the score by di * di.

Your task is to print an arrangement with as high a score as possible. Note that you can drop a person and don’t give him a vertice in the graph.

k, n, m = map(int, input().split())
input()
input()
for i in range(m):
    input()
print(' '.join(str(i) for i in range(1, k + 1)))