Link to problem: https://szkopul.edu.pl/problemset/problem/keHUVGyQb4AmzCAiUYjyPAnC/site/?key=statement

I think that the statement is concise enough so I will not restate it here.

Here is the link to the Polish solution. This problem is in pages 63-68:

https://oi.edu.pl/static/attachment/20110731/oi5.pdf

However, after reading this I still dont get the way to construct the similarity graph in polynomial complexity. Do anyone have an idea or code related to this problem??