https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_d
$N$頂点の完全グラフが与えられる。すべての辺に番号を振って、任意の頂点から同じ番号の辺だけを通ってもとの頂点に戻るような任意の経路の長さが偶数になるようにせよ。ただし、番号の最大値を最小化しなくてはならない。
二部グラフは、どの頂点から出発しても、もとの頂点に戻るための経路長が偶数になるようなグラフである（逆に、二部グラフではないグラフには必ず奇数長の閉路がある（たぶん））。よって、いくつかの二部グラフを重ね合わせて完全グラフを作れればよい。頂点集合を好きなように2つに分割して、異なる集合どうしにのみ辺を張れば二部グラフになる。$N$頂点の完全グラフを作るためには、いくつの二部グラフを重ねればよいだろうか？
$M$個の二部グラフを重ね合わせて$N$頂点の完全グラフを作ろうとするとき、$N$この頂点それぞれを"010...01"のようにグループ分けする必要がある。これは、$i$桁目が異なれば$i$番目の二部グラフにおいて異なる頂点集合に属することを意味しており、$i$桁目が異なる頂点どうしには$i$番目の二部グラフで辺を張ることができる。全点対間に辺を貼る必要があるので、グループ分けが全く同じ頂点が2つ以上あってはいけない。よって、$M$個の二部グラフで作れる完全グラフは$2^M$頂点までである。
実際に辺を貼る際には、頂点の番号を0-indexedで二進数表示したときに、$i$桁目が異なっていれば$i$番目の辺を張ればよい。
二部グラフを思いつかなかったのは悔しい。頂点を半分に分けていくという発想はあったのだが……。