俄羅斯娃娃是一種相當特別的木製玩具,通常有數個可以由中間轉開的娃娃,每個娃娃裡面又依序包含數個較小的娃娃。
據說你可以對俄羅斯娃娃許願,而許願的方法是把所有俄羅斯娃娃一一打開排好,默默許下自己的願望,接著威脅其中一隻娃娃,如果沒有實現願望,她這輩子都別想再看到太陽。接著再把俄羅斯娃娃一層一層收疊好,將被威脅的娃娃關在最裡面。所有俄羅斯娃娃會為了要救最裡面的娃娃出來,努力完成你的心願。
聽起來是個有點邪惡的許願方式,但是無論如何艾蜜莉決定一試,既然根據傳說,擁有越多層的俄羅斯娃娃,力量越強大,她決定將她所有蒐藏的俄羅斯娃娃全部展開,看看她可不可以將娃娃重新堆疊,組合出一隻有更多層的俄羅斯娃娃,釋放俄羅斯娃娃的洪荒之力(?
首先,她先測量每個娃娃的寬度和高度,因為她搜集的所有俄羅斯娃娃形狀都相同,所以如果有一個娃娃寬度是$w_1$高度是$h_1$,另外一個娃娃的寬度是$w_2$高度是$h_2$,那麼只要$w_1<w_2$而且$h_1<h_2$,第一個娃娃就可以被放進第二個娃娃中。
請你幫她算算看,根據她所擁有的這些俄羅斯娃娃,她最多可以堆疊出幾層的俄羅斯娃娃。
第一列包含一個正整數$t$ ($1\leq t\leq 20$),代表下面的測試資料數量
每筆測試資料前面都包含一個正整數$m$ ($1\leq m\leq 20000$),表示俄羅斯娃娃的數量
緊接著$2m$個正整數$w_1, h_1, w_2, h_2, \dots , w_m, h_m$,其中$w_i$和$h_i$分別表示第$i$個娃娃的寬度和高度 ($1\leq w_i,h_i\leq 1000$)
針對每一筆測資,輸出最多可以堆疊出幾層的俄羅斯娃娃
建國中學105學年度校隊選拔:初試pE
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~2 | $t,m\leq 10$ | 30 |
2 | 3~4 | $m\leq 100$ | 30 |
3 | 5~6 | 無額外限制 | 40 |