My solution can be found here. I got the hint from this code, thanks to bachbeo2007.
Here is the general idea of my solution. I send at most 8 messages based on the following table:
| Message | Range | Detail |
|---|---|---|
| 1 | $$$9800 \le i \lt 9960$$$ | To select 9801 nodes into 290+290. |
| 2 | $$$9960 \le i \lt 9985$$$ | To select 450+450 nodes into 45+45. |
| 3 | $$$9985 \le i \lt 9991$$$ | To select 70+70 nodes into 14+14. |
| 4 | $$$9991 \le i \lt 9995$$$ | To select 20+20 nodes into 5+5. |
| 5 | $$$9995 \le i \lt 9997$$$ | To select 9+9 nodes into 4+4. |
| 6 | $$$i = 9997$$$ | To select 24 pairs of nodes into 5. |
| 7 | $$$i = 9998$$$ | To select 10 pairs of nodes into 2. |
| 8 | $$$i = 9999$$$ | To select 5 pairs of nodes into 1. |
With the same idea, the maximum $$$N$$$ we can solve is $$$12201$$$ by adjusting the constants.



Note that, there is an edge appearing in 2 subgraphs and for each subgraph, there are 2 red nodes, 2 blue nodes, 1 green nodes, 4 edges connecting all pairs of red and blue nodes, and 1 edge connecting the green node to a red node.
Note that there is always a central node connecting 2 other nodes.





