I solved 1804F recently. It was a cute problem! But what made me curious was how the checker and generator works. It is clear that the $$$d(G)$$$ in the problem cannot be calculated by the checker every time when judging a submission, or the checker would TLE.

So there are extra lines in the input. They must be encoded and used to determine every $$$d(G)$$$. I guess that the checker&generator would work as one of the following two ways:

Method 1

• Determine every $$$d(G)$$$ in the beginning.
• Generate a graph satisfying the $$$d(G)$$$ constraint.
• Encode $$$d(G)$$$ and print them into the input.

Method 2

• Generate a graph randomly, and use brute force to calculate $$$d(G)$$$. If there is a way in $$$O(qn\text{polylog}n)$$$, it will cost only about $$$500s$$$ for every test case.
• Encode $$$d(G)$$$ and print them into the input.

For the checker, just read the encoded $$$d(G)$$$ from the input and decode them.

But for either of them I don't know the details (how to generate a graph according to $$$d(G)$$$, how the brute force works, ...). Anyone can explain to me? Maybe I should mention the author GlebsHP.