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??