Educational Codeforces Round 78 D. Segment Tree

問題文
codeforces.com

概要
n個の区間が与えられる. 区間ごとに番号をふり, 区間同士が交差するときその番号間に辺を張る. このようにしてできたグラフが木かどうか判定する.

考えたこと
まずNGパターンを考えると, サンプルにあるように閉路ができるパターンか頂点が連結でない場合がある.
NGが起こるような区間の組み合わせをうまく見つけられるか試したが, ダメそう

区間をl, rにわけイベントソートすれば, 辺の頂点の組が分かるので, 一度グラフを構築してそれが木構造か試す方針で進める.

TLEが出る.

適当な枝刈りをする（辺の数が頂点数-1を超えるとNGを出力）

AC

提出コード
codeforces.com

想定回でも操作を終了すること前提で話を進めていて泣いちゃった