解法
$ N \leq 60なら任意の$ i < jに対し$ x_jが$ x_iの倍数であるようなケースが作れるので、まずこの場合について考える。
思考の流れ :
あるラベルの辺だけに注目する
頂点が$ 0, 1, 2, 3のグループに分かれていて、$ a < bとなるグループ間にのみ辺が貼られているならば条件を満たす
$ 4^3 > N = 60なので、上手に$ 3つのラベルを組み合わせれば解けそう
$ i, jを$ 4進表記した際に$ 4^dの位が異なるような最大の$ dをとり、$ d + 1のラベルをつければよい。このとき$ i, jの$ 4^dの位をそれぞれ$ a, bとおくと$ 0 \leq a < b \leq 3が成り立つ。よって、同じラベルの辺を連続で$ 4回以上通ることはできない。
$ 4^3 > 60なので、$ 1, 2, 3のみで全ての辺をラベル付けできる。
一般の場合、$ Y_i = \lfloor \log_2X_i \rfloorとおき、$ i, jの$ 4進表記の代わりに$ Y_i, Y_jの$ 4進表記を利用すればよい。$ X_jが$ X_iの倍数ならば$ Y_j > Y_iなのでこの解法は正しい。
感想
$ N = 5, X = (1, 2, 4, 8, 16)とかで落ちる